HSG lớp 9 Nghệ An 2024-2025 (Bảng A)

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN ĐỀ CHÍNH THỨC
(Đề thi gồm 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 9 Năm học 2024 - 2025
Môn thi: Tin học - Bảng A
Thời gian làm bài: 150 phút (không kể thời gian giao đề)

---

Tổng quan bài thi

Tên bài	File nguồn	File Input	File Output	Bộ nhớ tối đa	Thời gian
SỐ CHÍNH PHƯƠNG	CHINHPHUONG.*	CHINHPHUONG.INP	CHINHPHUONG.OUT	1024MB	1 giây
CÂY THÔNG	CAYTHONG.*	CAYTHONG.INP	CAYTHONG.OUT	1024MB	1 giây
TRỒNG CÂY	TRONGCAY.*	TRONGCAY.INP	TRONGCAY.OUT	1024MB	1 giây
GIÁNG SINH	GIANGSINH.*	GIANGSINH.INP	GIANGSINH.OUT	1024MB	1 giây

Phần mở rộng .* được thay thế bằng Sb2 hoặc Sb3, Cpp, Py ứng với các ngôn ngữ lập trình Scratch, C++, Python.

Hãy lập trình giải các bài toán sau:

Câu 1. SỐ CHÍNH PHƯƠNG (6.0 điểm)

Trong buổi ôn tập hôm nay, thầy giáo đã chuẩn bị một số món quà để trao tặng cho các bạn trong đội tuyển học sinh giỏi trả lời đúng bài toán về số học của thầy như sau:

Cho hai số nguyên dương L, R (1 ≤ L ≤ R ≤ 10¹⁸). Hãy đếm số lượng số chính phương trong đoạn [L, R]?

Biết rằng số chính phương là số bằng bình phương của một số tự nhiên.

Ví dụ: 9 là số chính phương vì 9 = 3².

Rất nhanh chóng An đã đưa ra kết quả của bài toán. Em hãy lập trình giải quyết bài toán trên để biết xem An có được nhận món quà từ thầy giáo hay không.

Yêu cầu: Hãy đếm số lượng số chính phương trong đoạn [L, R].

Dữ liệu vào: Từ tệp văn bản CHINHPHUONG.INP chứa hai số nguyên dương L và R.

Kết quả: Ghi ra tệp CHINHPHUONG.OUT một số nguyên duy nhất là số lượng các số chính phương trong đoạn [L, R].

Ví dụ:

CHINHPHUONG.INP	CHINHPHUONG.OUT
4 30	4

Giới hạn:

• Có 70% test với 1 ≤ L ≤ R ≤ 10⁶;
• Có 30% test với 1 ≤ L ≤ R ≤ 10¹⁸.

Câu 2. CÂY THÔNG (5.0 điểm)

Chào đón Giáng sinh an lành, một cửa hàng có chương trình quà tặng đặc biệt. Lối vào của cửa hàng được trang trí bởi hai cây thông, cây thứ nhất treo n tấm thẻ có ghi các giá trị lần lượt là A₁, A₂, …, Aₙ; cây thứ hai cũng có n tấm thẻ có ghi các giá trị lần lượt là B₁, B₂, …, Bₙ. Người khách nào chọn được cặp thẻ Aᵢ và Bⱼ (1 ≤ i, j ≤ n) sao cho |Aᵢ + Bⱼ| đạt giá trị nhỏ nhất thì sẽ được tặng một cây thông mình thích nhất trong cửa hàng.

Yêu cầu: Em hãy giúp chủ cửa hàng xác định giá trị nhỏ nhất của |Aᵢ + Bⱼ| để tặng quà cho người khách lựa chọn được cặp thẻ thỏa mãn.

Dữ liệu vào: Từ tệp văn bản CAYTHONG.INP gồm:

• Dòng đầu tiên chứa một số nguyên dương n (1 ≤ n ≤ 10⁵)
• Dòng thứ hai chứa n số nguyên A₁, A₂, …, Aₙ (|Aᵢ| ≤ 10⁹)
• Dòng thứ ba chứa n số nguyên B₁, B₂, …, Bₙ (|Bᵢ| ≤ 10⁹)

Kết quả: Ghi ra tệp CAYTHONG.OUT một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

CAYTHONG.INP	CAYTHONG.OUT
5 -9 3 -17 -5 3 -1 7 2 3 20	2

Giới hạn:

• Có 60% test với 1 ≤ n ≤ 10³;
• Có 40% test với 10³ < n ≤ 10⁵.

Câu 3. TRỒNG CÂY (5.0 điểm)

An là chủ nhiệm của câu lạc bộ (CLB) Sống Xanh nơi mình sinh sống. Nhân dịp lễ Giáng sinh và chuẩn bị đón tết Nguyên đán, CLB phát động chiến dịch “Xanh quê hương” với nhiều hoạt động có ý nghĩa nhằm tạo môi trường Xanh – Sạch – Đẹp. Hoạt động đầu tiên trong chiến dịch là thực hiện trồng một hàng cây chạy dọc theo một tuyến đường.

Trên tuyến đường đã được đánh dấu n vị trí cách đều nhau để trồng cây, trong đó có một số vị trí đã được trồng cây từ trước. CLB gồm An và k thành viên sẽ trồng k + 1 cây vào k + 1 vị trí trống (mỗi người trồng một cây). Để thuận tiện quản lí, An muốn tìm một vị trí trồng cây của mình và vị trí của k thành viên, sao cho khoảng cách từ vị trí thành viên xa nhất đến vị trí của An là ngắn nhất.

Yêu cầu: Hãy lập trình giúp An xác định giá trị nhỏ nhất của khoảng cách từ vị trí thành viên xa nhất đến vị trí của An.

Dữ liệu vào: Từ tệp văn bản TRONGCAY.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương n, k (1 ≤ k < n ≤ 10⁵)
• Dòng thứ hai chứa một xâu nhị phân s gồm n phần tử biểu diễn trạng thái của n vị trí. Giá trị 0 biểu diễn vị trí trống, giá trị 1 biểu diễn vị trí đã có cây trồng.

(Dữ liệu đảm bảo số phần tử có giá trị 0 trong xâu s luôn lớn hơn k)

Kết quả: Ghi ra tệp TRONGCAY.OUT một số nguyên dương là giá trị nhỏ nhất của khoảng cách từ vị trí thành viên xa nhất đến vị trí của An.

Ví dụ:

TRONGCAY.INP	TRONGCAY.OUT	Giải thích
7 2 1010100	2	- Cách 1: Chọn các vị trí 2; 4; 6. An ở vị trí số 4 và khoảng cách đến thành viên xa nhất là |6 − 4| = |2 − 4| = 2. - Cách 2: Chọn các vị trí 4; 6; 7. An ở vị trí số 6 và khoảng cách đến thành viên xa nhất là |4 − 6| = 2. Vậy An có thể chọn theo cách 1 hoặc cách 2 đều cho khoảng cách là 2; các cách chọn khác đều cho khoảng cách lớn hơn 2.

Giới hạn:

• Có 60% test với 1 < n ≤ 10³;
• Có 40% test với 10³ < n ≤ 10⁵.

Câu 4. GIÁNG SINH (4.0 điểm)

Giáng sinh là khoảng thời gian đẹp nhất trong năm. Hai anh em Wiliam và Jacica là hai diễn viên múa chính của đoàn nghệ thuật đỉnh cao số một thế giới. Các vở diễn của họ góp phần hồi sinh các giá trị đạo đức, văn hóa truyền thống, đem lại cho người xem năng lượng tích cực, cảm nhận sâu sắc về các giá trị tốt đẹp và sự bình yên trong tâm hồn. Wiliam và Jacica vừa trở về nhà sau chuyến lưu diễn vòng quanh thế giới và bắt đầu trang trí cây thông Noel của họ bằng những món đồ xinh xắn đã mua trong quá trình lưu diễn.

Họ đã mua n món đồ trang trí cây thông được xếp cạnh nhau trong một hộp dài, món đồ trang trí thứ i có màu Aᵢ. Hộp được mở ở cả hai đầu, vì vậy các món đồ có thể được lấy ra từ bên trái hoặc bên phải của hộp. Hộp này trong suốt, nên Wiliam và Jacica có thể nhìn thấy màu sắc của từng món đồ trang trí.

Jacica nghĩ ra một trò chơi để việc trang trí cây thông trở nên thú vị hơn. Trò chơi diễn ra như sau: Wiliam và Jacica thay phiên nhau chơi, Wiliam là người bắt đầu. Người chơi trong lượt của mình sẽ lấy một món đồ trang trí từ hộp (có thể từ bên trái hoặc bên phải) và đặt nó lên cây thông. Nếu món đồ được lấy có màu chưa từng được người nào lấy trước đó, người chơi sẽ ghi được một điểm. Trò chơi kết thúc khi món đồ trang trí cuối cùng được lấy ra khỏi hộp.

Người chiến thắng là người ghi được nhiều điểm hơn. Vì cả Wiliam và Jacica đều là những người chơi xuất sắc, họ sẽ chơi một cách tối ưu.

Yêu cầu: Em hãy đưa ra kết quả cuối cùng của trò chơi.

Dữ liệu vào: Từ tệp văn bản GIANGSINH.INP gồm:

• Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 3000) là số lượng món đồ trang trí trong hộp.
• Dòng thứ hai chứa n số nguyên A₁, A₂, …, Aₙ với Aᵢ (1 ≤ Aᵢ ≤ n) là màu sắc của món đồ thứ i.

Kết quả: Ghi ra tệp GIANGSINH.OUT một dòng duy nhất gồm hai số, được nối bằng một ký tự ”:” (dấu hai chấm), lần lượt là điểm số của Wiliam và Jacica.

Ví dụ:

GIANGSINH.INP	GIANGSINH.OUT
5 1 1 2 1 1	1:1
6 5 3 4 5 3 4	2:1

Giải thích test ở ví dụ 1: Wiliam và Jacica có thể chơi theo cách sau (hộp ban đầu: 1 1 2 1 1):

Hộp trước lượt	Diễn biến
1 1 2 1 1	Đầu tiên Wiliam chọn món đồ có màu 1 ở bên trái và được 1 điểm.
1 2 1 1	Tiếp theo Jacica chọn món đồ có màu 1 ở bên phải và không có điểm vì màu 1 đã được lấy.
1 2 1	Tiếp theo Wiliam chọn màu 1 ở về bên trái và không được tăng thêm điểm vì màu 1 đã được lấy.
2 1	Tiếp theo Jacica lấy màu 2 ở về bên trái và được 1 điểm vì màu 2 chưa từng được lấy.
1	Cuối cùng Wiliam lấy màu 1 và không được tăng thêm điểm vì màu 1 đã được lấy.

Vậy kết quả cuối cùng ở ví dụ 1 là: 1:1

Giới hạn:

• Có 25% test với 1 ≤ Aᵢ ≤ 2 với mọi i từ 1 đến n;
• Có 20% test với 1 ≤ n ≤ 20;
• Có 10% test với 1 ≤ Aᵢ ≤ 20 với mọi i từ 1 đến n;
• Có 20% test với 1 ≤ n ≤ 300;
• Có 25% test với 300 < n ≤ 3000.

---

Hết