HSG THCS Khánh Hòa 2023-2024

SỞ GIÁO DỤC VÀ ĐÀO TẠO KHÁNH HÒA ĐỀ THI CHÍNH THỨC
(Đề thi có 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI THCS CẤP TỈNH Năm học 2023 - 2024
Môn thi: Tin học - Ngày thi: 07/12/2023
Thời gian: 150 phút (không kể thời gian phát đề)

---

Tổng quan về đề thi

Bài	Tên bài	Tên tệp chương trình	Tên tệp dữ liệu vào	Tên tệp kết quả	Thời gian
1	Đếm gạo	DEMGAO.*	DEMGAO.INP	DEMGAO.OUT	1 giây/test
2	Từ dài	TUDAI.*	TUDAI.INP	TUDAI.OUT	1 giây/test
3	Cửa sổ	CUASO.*	CUASO.INP	CUASO.OUT	1 giây/test
4	Số nguyên tố toàn diện	SNTOTD.*	SNTOTD.INP	SNTOTD.OUT	1 giây/test

Dấu * được thay thế bởi PAS hoặc CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++ hoặc Python.

Các số trên cùng một dòng trong tệp dữ liệu vào/ra được ghi cách nhau ít nhất một dấu cách.

Bài 1. Đếm gạo (6,0 điểm)

Nấm là cô bé đáng yêu và tốt bụng. Cô bé đặc biệt thích truyện cổ tích. Vì thế, đêm qua, Nấm nằm mơ về nàng Lọ Lem. Trong giấc mơ, Lọ Lem không bị mụ dì ghẻ bắt phân loại các loại đậu nữa mà bắt nhặt gạo. Có rất nhiều gạo trong kho, các hạt gạo đã được đánh số thứ tự là số nguyên liên tiếp từ a tới b. Mụ bắt nàng phải nhặt ra các hạt gạo có số thứ tự là bội của một số k cho trước. Đồng thời sau khi nhặt xong phải trả lời cho mụ biết số lượng hạt gạo nhặt được. Việc nhặt gạo thì quá đơn giản, chỉ trong tích tắc bầy chim đã giúp nàng nhặt xong. Bây giờ nhiệm vụ của Nấm là đếm số lượng hạt gạo đã nhặt được. Thật không may, chưa đếm xong thì Nấm đã tỉnh dậy. Nấm rất muốn có câu trả lời cho Lọ Lem.

Yêu cầu: Hãy trả lời giúp Nấm, nếu hoàn thành phần việc của mình, Nấm sẽ đếm được bao nhiêu hạt gạo?

Dữ liệu vào: Từ tệp văn bản DEMGAO.INP gồm ba số nguyên dương a, b và k ghi trên cùng 1 dòng (1 ≤ a ≤ b ≤ 10¹⁸; 1 ≤ k ≤ 10¹⁸).

Kết quả: Ghi ra tệp văn bản DEMGAO.OUT một số nguyên duy nhất là kết quả cần tìm.

Ví dụ 1:

DEMGAO.INP	DEMGAO.OUT	Giải thích
3 10 5	2	Hai hạt gạo được nhặt là hạt có số thứ tự 5 và hạt có số thứ tự 10.

Ví dụ 2:

DEMGAO.INP	DEMGAO.OUT	Giải thích
6 9 5	0	Không có hạt gạo nào thỏa mãn yêu cầu cần nhặt.

Ràng buộc:

• 70% số test tương ứng với 70% số điểm có 1 ≤ a ≤ b ≤ 10⁶.
• 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.

Bài 2. Từ dài (5,0 điểm)

Một từ được định nghĩa là một hoặc một dãy các kí tự liên tiếp nhau và không chứa dấu cách (kí tự trắng). Độ dài của một từ là số kí tự có trong từ đó.

Cho xâu gồm các kí tự ‘A’..‘Z’, ‘a’..‘z’, ‘0’..‘9’, kí tự trắng (dấu cách).

Yêu cầu: Tìm độ dài của từ có nhiều kí tự nhất và từ tương ứng với độ dài đó.

Dữ liệu vào: Từ tệp văn bản TUDAI.INP gồm 1 dòng duy nhất chứa xâu (độ dài xâu không quá 255 kí tự và trong xâu chứa ít nhất một từ).

Kết quả: Ghi ra tệp văn bản TUDAI.OUT gồm 2 dòng:

• Dòng 1: Ghi độ dài của từ có nhiều kí tự nhất (độ dài lớn nhất).
• Dòng 2: Ghi từ có độ dài lớn nhất.

Lưu ý: nếu có nhiều từ có cùng độ dài lớn nhất thì ghi từ có độ dài lớn nhất sau cùng trong xâu.

Ví dụ:

TUDAI.INP	TUDAI.OUT
Khanh_Hoa que huong toi	5 huong

Ghi chú

Ví dụ trong đề gốc có ký tự “_” (không nằm trong tập ký tự đề cho) và kết quả “huong” chứ không phải “Khanh_Hoa” - nhiều khả năng xâu gốc là Khanh Hoa que huong toi.

Bài 3. Cửa sổ (5,0 điểm)

Tí đang chơi trò ghép nhà từ những que tính. Phần căn nhà đã được ghép xong, chỉ còn thiếu một cửa sổ hình chữ nhật. Hiện tại, Tí còn dư n que tính, các que tính được đánh số thứ tự từ 1 tới n, que thứ i có độ dài aᵢ (đơn vị đo chiều dài). Tí muốn ghép được cửa sổ càng to càng tốt. Một cửa sổ sẽ được ghép từ 4 que tính.

Yêu cầu: Hãy cho biết chu vi của cửa sổ lớn nhất mà Tí có thể ghép được.

Lưu ý: Không bẻ gãy hay chắp nối để thay đổi chiều dài que tính và hình vuông cũng được xem là hình chữ nhật.

Dữ liệu vào: Từ tệp văn bản CUASO.INP gồm 2 dòng:

• Dòng đầu chứa số nguyên dương n (1 ≤ n ≤ 10⁶).
• Dòng thứ hai chứa n số nguyên dương aᵢ (1 ≤ aᵢ ≤ 10⁶; 1 ≤ i ≤ n).

Kết quả: Ghi ra tệp văn bản CUASO.OUT số nguyên duy nhất là chu vi lớn nhất của cửa sổ có thể ghép được. Nếu không thể ghép được thì ghi −1.

Ví dụ 1:

CUASO.INP	CUASO.OUT	Giải thích
7 3 8 4 3 8 1 1	22	Có 3 cách ghép thành cửa sổ là cửa sổ có chiều dài và chiều rộng như sau: (8, 3); (3, 1); (8, 1). Chu vi lớn nhất là (3 + 8) × 2 = 22

Ví dụ 2:

CUASO.INP	CUASO.OUT	Giải thích
5 4 9 1 9 3	-1	Không thể ghép thành cửa sổ nào cả.

Ràng buộc:

• 30% số test tương ứng với 30% số điểm có n ≤ 50.
• 40% số test tương ứng với 40% số điểm có 50 < n ≤ 1000.
• 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.

Bài 4. Số nguyên tố toàn diện (4,0 điểm)

Hôm nay, An được học về số nguyên tố. Số nguyên tố là số có đúng hai ước nguyên dương là 1 và chính nó. Ví dụ số 17 là số nguyên tố nhưng số 16 thì không.

Vốn là người có nhiều ý tưởng sáng tạo, An đưa ra một khái niệm mới gọi là “số nguyên tố toàn diện”. Một số nguyên dương x gọi là số nguyên tố toàn diện nếu thỏa mãn đồng thời 3 điều kiện sau:

• x là số nguyên tố.
• Lần lượt bỏ đi các chữ số bên phải của x thì phần còn lại của nó vẫn là số nguyên tố.
• Thêm vào bên phải của x một trong các chữ số từ 0 tới 9, số thu được cũng là số nguyên tố.

Ví dụ số 313 là số nguyên tố toàn diện vì:

• 313 là số nguyên tố.
• Bỏ đi số 3 bên phải ta còn số 31 là số nguyên tố, bỏ tiếp số 1 ta còn số 3 cũng là số nguyên tố.
• Thêm số 7 vào sau 313 ta được số 3137 là số nguyên tố.

Yêu cầu: Cho dãy A gồm n số nguyên dương a₁, a₂, …, aₙ và m câu hỏi. Mỗi câu hỏi có dạng (u, v) với ý nghĩa: Đếm số lượng số nguyên tố toàn diện trong dãy A từ vị trí u tới vị trí v.

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

• Dòng đầu chứa số nguyên n (1 ≤ n ≤ 10⁵).
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁶; 1 ≤ i ≤ n).
• Dòng thứ ba chứa số nguyên m là số lượng câu hỏi (1 ≤ m ≤ 10⁵).
• m dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v (1 ≤ u ≤ v ≤ n).

Kết quả: Ghi ra tệp văn bản SNTOTD.OUT m dòng, mỗi dòng là đáp án của một câu hỏi theo thứ tự của các câu hỏi được đưa ra trong tệp dữ liệu vào.

Ví dụ:

SNTOTD.INP	SNTOTD.OUT	Giải thích
6 59 12 57 53 23 313 3 1 3 2 5 3 6	1 1 2	- Có 1 số nguyên tố toàn diện là 59 trong đoạn từ 1 tới 3. - Có 1 số nguyên tố toàn diện là 23 trong đoạn từ 2 tới 5. - Có 2 số nguyên tố toàn diện là 23 và 313 trong đoạn từ 3 tới 6.

Ràng buộc:

• 70% số test tương ứng với 70% số điểm có 1 ≤ n ≤ 10³; 1 ≤ aᵢ ≤ 10³; 1 ≤ m ≤ 10³.
• 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.

---

Giám thị không giải thích gì thêm.