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

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

ĐỀ SỐ 22 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	Chữ số 0 tận cùng của giai thừa	`GIAITHUA.*`	`GIAITHUA.INP`	`GIAITHUA.OUT`	4
2	Từ được dùng nhiều nhất	`TUDAINHAT.*`	`TUDAINHAT.INP`	`TUDAINHAT.OUT`	4
3	Leo cầu thang	`CAUTHANG.*`	`CAUTHANG.INP`	`CAUTHANG.OUT`	6
4	Mảnh đất hình vuông	`HINHVUONG.*`	`HINHVUONG.INP`	`HINHVUONG.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. Chữ số 0 tận cùng của giai thừa (4 điểm)

Giai thừa của n là n! = 1 × 2 × … × n (quy ước 0! = 1). Ví dụ 10! = 3 628 800 có 2 chữ số 0 tận cùng.

Yêu cầu:

Cho biết n! có bao nhiêu chữ số 0 tận cùng.
Tìm số tự nhiên m nhỏ nhất sao cho m! có ít nhất z chữ số 0 tận cùng.

Dữ liệu vào: Từ file văn bản GIAITHUA.INP gồm một dòng chứa hai số tự nhiên n và z.

Kết quả: Ghi ra file văn bản GIAITHUA.OUT gồm hai dòng lần lượt là đáp án hai câu.

Ví dụ:

GIAITHUA.INP	GIAITHUA.OUT	Giải thích
`25 6`	`6` `25`	25! có 6 chữ số 0 tận cùng; 24! chỉ có 4 chữ số 0 tận cùng.

Ràng buộc:

Có 50% số test với n ≤ 1000, z ≤ 200.
Có 50% số test với n ≤ 10¹⁸, z ≤ 10¹⁷.

Bài 2. Từ được dùng nhiều nhất (4 điểm)

Cho một đoạn văn tiếng Việt không dấu (có thể gồm nhiều dòng). Từ là một dãy chữ cái tiếng Anh liên tiếp; mọi kí tự khác chữ cái (dấu cách, dấu câu, chữ số, xuống dòng) đều là dấu ngăn cách. Không phân biệt chữ hoa và chữ thường (Hoc và hoc là cùng một từ).

Yêu cầu: Cho biết đoạn văn có bao nhiêu từ khác nhau, và từ nào xuất hiện nhiều nhất (viết in thường; nếu có nhiều từ như vậy thì chọn từ nhỏ nhất theo thứ tự từ điển).

Dữ liệu vào: Từ file văn bản TUDAINHAT.INP gồm đoạn văn (có ít nhất một chữ cái).

Kết quả: Ghi ra file văn bản TUDAINHAT.OUT gồm hai dòng: số từ khác nhau; từ xuất hiện nhiều nhất và số lần xuất hiện của nó.

Ví dụ:

TUDAINHAT.INP	TUDAINHAT.OUT	Giải thích
`Hoc, hoc nua, hoc mai! Hoc de biet.`	`5` `hoc 4`	Các từ khác nhau: hoc, nua, mai, de, biet.

Ràng buộc: Gọi L là tổng số kí tự của đoạn văn.

Có 50% số test với L ≤ 1000.
Có 50% số test với L ≤ 10⁶.

Bài 3. Leo cầu thang (6 điểm)

Một cầu thang có n bậc, đánh số từ 1 đến n; bạn Bin đứng ở mặt đất (bậc 0) và muốn lên đúng bậc thứ n. Mỗi bước Bin có thể leo lên 1, 2 hoặc 3 bậc. Có m bậc bị hỏng, Bin không được đặt chân lên các bậc đó (bậc n không hỏng).

Yêu cầu: Đếm số cách để Bin lên được bậc n. Vì kết quả có thể rất lớn, hãy ghi phần dư khi chia cho 10⁹ + 7.

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

Dòng đầu tiên chứa hai số nguyên n và m.
Dòng thứ hai chứa m số nguyên đôi một khác nhau là các bậc bị hỏng (nằm trong khoảng từ 1 đến n − 1). Nếu m = 0 thì dòng này để trống.

Kết quả: Ghi ra file văn bản CAUTHANG.OUT một số nguyên là số cách (chia lấy dư cho 10⁹ + 7).

Ví dụ:

CAUTHANG.INP	CAUTHANG.OUT	Giải thích
`5 1` `3`	`5`	0→1→2→4→5, 0→1→2→5, 0→1→4→5, 0→2→4→5, 0→2→5.
`4 0` (dòng trống)	`7`

Ràng buộc:

Có 30% số test với n ≤ 20.
Có 70% số test với n ≤ 10⁶.

Bài 4. Mảnh đất hình vuông (6 điểm)

Một khu đất được chia thành lưới m × n ô, ô ghi 1 là đất tốt, ô ghi 0 là đất xấu. Người ta muốn chọn một mảnh đất hình vuông (các cạnh song song với lưới) gồm toàn đất tốt, càng lớn càng tốt.

Yêu cầu: Tìm cạnh của mảnh đất hình vuông lớn nhất và vị trí góc trên trái của nó (nếu có nhiều vị trí thì chọn hàng nhỏ nhất, rồi đến cột nhỏ nhất).

Dữ liệu vào: Từ file văn bản HINHVUONG.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 gồm n kí tự 0 hoặc 1.

Kết quả: Ghi ra file văn bản HINHVUONG.OUT: nếu không có ô đất tốt nào thì ghi 0. Ngược lại, dòng thứ nhất ghi cạnh hình vuông lớn nhất, dòng thứ hai ghi hàng và cột của góc trên trái.

Ví dụ:

HINHVUONG.INP	HINHVUONG.OUT
`4 5` `10100` `10111` `11111` `10010`	`2` `2 3`

Ràng buộc:

Có 30% số test với m, n ≤ 30.
Có 30% số test với m, n ≤ 100.
Có 40% số test với m, n ≤ 500.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English