Đề số 23 - Ôn thi HSG Tin học THCS

BỘ ĐỀ ÔN THI HỌC SINH GIỎI TIN HỌC THCS Bumbii Academy

ĐỀ SỐ 23 Thời gian làm bài: 150 phút
4 bài, tổng 20 điểm

---

Tổng quan đề thi

Bài	Tên bài	File chương trình	File dữ liệu vào	File kết quả	Điểm
1	Dấu hiệu chia hết	CHIAHET3.*	CHIAHET3.INP	CHIAHET3.OUT	3
2	Dãy ngoặc	NGOAC.*	NGOAC.INP	NGOAC.OUT	5
3	Đổi xu	DOIXU.*	DOIXU.INP	DOIXU.OUT	6
4	Robot nhặt xu	DUONGDI.*	DUONGDI.INP	DUONGDI.OUT	6

Dấu * được thay bằng py hoặc cpp tùy theo ngôn ngữ lập trình sử dụng.

Bài 1. Dấu hiệu chia hết (3 điểm)

Yêu cầu: Cho số nguyên dương n (có thể rất lớn). Tính tổng các chữ số của n và cho biết n có chia hết cho 3, cho 9, cho 11 hay không.

Dữ liệu vào: Từ file văn bản CHIAHET3.INP gồm một số nguyên dương n (không có chữ số 0 ở đầu).

Kết quả: Ghi ra file văn bản CHIAHET3.OUT gồm hai dòng: dòng thứ nhất ghi tổng các chữ số; dòng thứ hai ghi ba từ YES hoặc NO lần lượt cho các câu hỏi chia hết cho 3, 9, 11.

Ví dụ:

CHIAHET3.INP	CHIAHET3.OUT	Giải thích
918082	28 NO NO YES	918082 = 11 × 83462.

Ràng buộc:

• Có 50% số test với n ≤ 10¹⁸.
• Có 50% số test với n có tới 10⁵ chữ số.

Bài 2. Dãy ngoặc (5 điểm)

Dãy ngoặc đúng được định nghĩa: xâu rỗng là dãy ngoặc đúng; nếu A, B là dãy ngoặc đúng thì (A), [A], {A} và AB cũng là dãy ngoặc đúng. Độ sâu của dãy ngoặc đúng là số ngoặc mở lồng nhau nhiều nhất tại một thời điểm.

Yêu cầu: Cho xâu S gồm các kí tự (, ), [, ], {, }. Nếu S là dãy ngoặc đúng, cho biết độ sâu của nó. Ngược lại, cho biết vị trí lỗi đầu tiên, xác định như sau:

• Đọc S từ trái sang. Nếu gặp một ngoặc đóng mà không có ngoặc mở tương ứng đang chờ (hoặc ngoặc mở gần nhất đang chờ khác loại), thì vị trí lỗi là vị trí của ngoặc đóng đó.
• Nếu đọc hết S mà không gặp lỗi như trên nhưng vẫn còn ngoặc mở chưa được đóng, thì vị trí lỗi là vị trí của ngoặc mở sớm nhất trong số đó.

Dữ liệu vào: Từ file văn bản NGOAC.INP gồm một dòng chứa xâu S.

Kết quả: Ghi ra file văn bản NGOAC.OUT gồm hai dòng: YES và độ sâu, hoặc NO và vị trí lỗi (các vị trí đánh số từ 1).

Ví dụ:

NGOAC.INP	NGOAC.OUT	Giải thích
([]{()})	YES 3	Ngoặc ( trong cùng nằm ở độ sâu 3.
(()))(	NO 5	Ngoặc ) ở vị trí 5 không có ngoặc mở tương ứng.
{[}]	NO 3	Ngoặc } ở vị trí 3 không khớp với [ đang chờ.

Ràng buộc: Gọi L là độ dài xâu S.

• Có 40% số test với S chỉ gồm ( và ), L ≤ 1000.
• Có 60% số test với L ≤ 10⁶.

Bài 3. Đổi xu (6 điểm)

Một nước có n loại đồng xu với mệnh giá c₁, c₂, …, c_n (đôi một khác nhau), mỗi loại có số lượng không giới hạn.

Yêu cầu:

1. Tìm số đồng xu ít nhất để trả đúng số tiền S.
2. Đếm số cách trả đúng số tiền S (hai cách khác nhau nếu số lượng dùng của ít nhất một loại xu khác nhau, không quan tâm thứ tự đưa xu). Ghi phần dư khi chia cho 10⁹ + 7.

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

• Dòng đầu tiên chứa hai số nguyên dương n và S.
• Dòng thứ hai chứa n số nguyên dương c₁, c₂, …, c_n (c_i ≤ 10⁴).

Kết quả: Ghi ra file văn bản DOIXU.OUT gồm hai dòng lần lượt là đáp án hai câu. Nếu không trả được đúng số tiền S thì dòng thứ nhất ghi -1 (khi đó số cách bằng 0).

Ví dụ:

DOIXU.INP	DOIXU.OUT	Giải thích
3 6 1 3 4	2 4	6 = 3 + 3 (2 đồng xu). Các cách: 1×6; 3 + 1×3; 3 + 3; 4 + 1 + 1.
2 7 2 4	-1 0	Chỉ trả được số tiền chẵn.

Ràng buộc:

• Có 30% số test với n ≤ 4, S ≤ 60.
• Có 70% số test với n ≤ 50, S ≤ 10⁴.

Bài 4. Robot nhặt xu (6 điểm)

Một robot đi trên lưới m hàng, n cột, xuất phát từ ô (1, 1) và cần đến ô (m, n). Mỗi bước robot chỉ được đi sang phải hoặc xuống dưới một ô. Ô ghi # là vật cản, robot không được đi vào; ô ghi chữ số d (0…9) có d đồng xu, robot đi qua thì nhặt được hết.

Yêu cầu: Đếm số đường đi khác nhau từ (1, 1) đến (m, n) (chia lấy dư cho 10⁹ + 7), và tìm số xu nhiều nhất robot có thể nhặt được (tính cả ô xuất phát và ô đích).

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

• Dòng đầu tiên chứa hai số nguyên dương m, n.
• m dòng tiếp theo, mỗi dòng là một xâu n kí tự (chữ số hoặc #). Ô (1, 1) và ô (m, n) không phải vật cản.

Kết quả: Ghi ra file văn bản DUONGDI.OUT gồm hai dòng: số đường đi và số xu nhiều nhất. Nếu không có đường đi nào thì ghi 0 và -1.

Ví dụ:

DUONGDI.INP	DUONGDI.OUT
3 4 1203 0#51 2410	4 9

Ràng buộc:

• Có 30% số test với m, n ≤ 8.
• Có 70% số test với m, n ≤ 500.

Lời giải và bộ test của đề này (có phí)

Hướng dẫn giải chi tiết, code Python và C++ đã được kiểm chứng, cùng bộ test và công cụ chấm cham.py, có trong bộ tài liệu đầy đủ (có phí).

Thầy cô và các em muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.

Muốn xem trước cách trình bày lời giải, hãy xem Đề số 01 (có lời giải miễn phí).

Do số lượng đề bài, bài giải và bộ test rất nhiều nên tác giả đang kiểm tra từng bước. Thầy cô và các em học sinh nếu thấy sai sót xin vui lòng liên hệ tác giả qua Facebook hoặc Zalo (0972465159). Xin chân thành cảm ơn.