HSG lớp 9 TP. Hồ Chí Minh 2023-2024

SỞ GIÁO DỤC VÀ ĐÀO TẠO THÀNH PHỐ HỒ CHÍ MINH ĐỀ THEO TRÍ NHỚ CỦA ĐỘI TUYỂN HỒNG BÀNG
(Đề thi gồm 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP THÀNH PHỐ Năm học 2023 - 2024
Môn: Tin học - Ngày thi: 19/3/2024
Thời gian làm bài: 120 phút (không tính thời gian phát đề)

---

Chú ý

Đây là đề được đội tuyển trường Hồng Bàng ghi lại theo trí nhớ sau kỳ thi, không phải bản đề chính thức, nên một số chi tiết (ràng buộc, ví dụ) có thể chưa chính xác hoàn toàn.

Tổng quan bài thi

Tên bài	Tập tin chương trình	Tập tin dữ liệu	Tập tin kết quả
ROBOT	ROBOT.*	ROBOT.INP	ROBOT.OUT
DÃY CON	DAYCON.*	DAYCON.INP	DAYCON.OUT
SDIGIT	SDIGIT.*	SDIGIT.INP	SDIGIT.OUT

Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++. Các tập tin chương trình lưu trong cùng một thư mục với tên thư mục là TIN<số báo danh>. Ví dụ: thí sinh có số báo danh là 1234 thì tên thư mục là TIN1234.

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

Bài 1. Robot (7 điểm)

Một con ROBOT được làm bởi đội tuyển robot trường Hồng Bàng đang thực hiện nhiệm vụ trên một hành tinh xa xôi nào đó. Tuy nhiên do một cơn bão lớn đã làm hư bảng mạch của ROBOT, giờ đây ROBOT chỉ có thể đi qua phải a hoặc b ô hoặc đi lên c hoặc d ô theo sự điều khiển. Đội tuyển robot trường Hồng Bàng không biết có thể điều khiển robot đi từ ô trái dưới đến ô phải trên hay không và làm sao để có thể điều khiển ROBOT đi với số lần điều khiển là ít nhất.

Yêu cầu: Hãy viết chương trình giúp đội tuyển robot trường Hồng Bàng tìm được số lần điều khiển ít nhất mà ROBOT cần để đến được đích. Nếu không đi được thì hãy xuất ra −1.

Dữ liệu: Vào từ file văn bản ROBOT.INP gồm

• Dòng thứ nhất chứa số nguyên N (1 ≤ N ≤ 10⁶)
• Dòng thứ hai chứa 2 số nguyên a và b
• Dòng thứ ba chứa 2 số nguyên c và d

Các số trên cùng 1 dòng thì cách nhau 1 khoảng trắng và (0 ≤ a, b, c, d ≤ 10⁹).

Kết quả: Ghi ra file văn bản ROBOT.OUT 1 số nguyên duy nhất là số lần điều khiển ít nhất để ROBOT có thể đến đích, nếu không được thì ghi ra −1.

Ràng buộc:

• 60% Subtask 1: 1 ≤ N ≤ 10
• 90% Subtask 2: 1 ≤ N ≤ 10⁴
• 100% Subtask 3: 1 ≤ N ≤ 10⁶

Ví dụ 1:

ROBOT.INP	ROBOT.OUT
5 2 3 4 5	3

Giải thích ví dụ 1:

• Ở lượt đầu robot đi qua phải 2 ô
• Ở lượt hai robot đi lên 4 ô
• Ở lượt ba robot đi qua phải 2 ô

Ví dụ 2:

ROBOT.INP	ROBOT.OUT
5 8 3 3 2	-1

Giải thích ví dụ 2: Vì robot không thể đi qua phải được 8 ô vì (8 > 5) và không đi lên 3 ô được vì 5 % 3 != 0.

Ghi chú

Theo ví dụ, lưới có kích thước N × N và robot cần đi từ ô (1, 1) đến ô (N, N), tức là đi sang phải tổng cộng N − 1 ô và đi lên tổng cộng N − 1 ô.

Bài 2. Dãy con (7 điểm)

Trong giờ học toán Minh đã được học một kiến thức mới là dãy con. Minh được thầy giao nhiệm vụ như sau: Cho dãy A có n phần tử, tìm số dãy con liên tiếp trong dãy A sao cho tổng của chúng không nhỏ hơn một số k.

Yêu cầu: Các em hãy lập trình giúp Minh tìm ra số dãy con thỏa nhiệm vụ của thầy dạy toán.

Dữ liệu: Vào từ file văn bản DAYCON.INP

• Dòng đầu là hai số n, k (k ≤ 10⁹).
• Dòng sau chứa n số của dãy A (1 ≤ Aᵢ ≤ 10⁹).

Kết quả: Ghi ra file văn bản DAYCON.OUT

• Số dãy con liên tiếp có tổng không nhỏ hơn k.

Ràng buộc:

• 30% Subtask 1: 1 ≤ N ≤ 10
• 60% Subtask 2: 1 ≤ N ≤ 10⁴
• 100% Subtask 3: 1 ≤ N ≤ 10⁵

Ví dụ:

DAYCON.INP	DAYCON.OUT	Giải thích
5 6 1 2 1 4 5	6	Có 6 dãy sau có tổng không nhỏ hơn 6: [1, 2, 1, 4, 5]; [1, 2, 1, 4]; [2, 1, 4]; [2, 1, 4, 5]; [1, 4, 5]; [4, 5].

Bài 3. Số SDIGIT (6 điểm)

Minh đang nghiên cứu về số học thì thấy rất thích các số có tổng các chữ số là số nguyên tố. Minh gọi các số đó là SDIGIT.

Một số có k chữ số thì gọi là số có độ dài k. Minh đang có nhiệm vụ đi tìm tất cả các số SDIGIT có độ dài từ l đến r. Vì số lượng số SDIGIT quá nhiều nên anh ấy không đếm nổi được.

Yêu cầu: Hãy viết một chương trình giúp Minh biết từ độ dài lᵢ đến rᵢ có bao nhiêu số mà tổng các chữ số của chúng là 1 số nguyên tố.

Dữ liệu: Vào từ file văn bản SDIGIT.INP

• Dòng đầu là số q - số truy vấn cần thực hiện.
• q dòng sau, dòng thứ i chứa 2 số lᵢ, rᵢ.

Kết quả: Ghi ra file văn bản SDIGIT.OUT

• Mỗi dòng i là một đáp án cho truy vấn thứ i.

Ràng buộc:

• 80% số điểm của bài: 1 ≤ lᵢ, rᵢ ≤ 6, q ≤ 10.
• 100% số điểm của bài: 1 ≤ lᵢ, rᵢ ≤ 250, q = 1.

Ví dụ:

SDIGIT.INP	SDIGIT.OUT	Giải thích
2 1 1 1 2	4 37	Các số có độ dài 1 là 1 → 9. Trong đó số SDIGIT là: 2, 3, 5, 7. Các số có độ dài 1 và 2 là 1 → 99. Trong đó số SDIGIT là: 2, 3, 5, 7, 11, 12, 14, 16, 20, … 89, 92, 94, 98.

---

(Cán bộ coi thi không giải thích gì thêm)