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

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

ĐỀ SỐ 30 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	Đánh số trang	`DANHSO.*`	`DANHSO.INP`	`DANHSO.OUT`	4
2	Mật mã Vigenère	`MAHOA.*`	`MAHOA.INP`	`MAHOA.OUT`	5
3	Chuỗi ngày đạt chỉ tiêu	`DOANTB.*`	`DOANTB.INP`	`DOANTB.OUT`	5
4	Phá tường	`PHATUONG.*`	`PHATUONG.INP`	`PHATUONG.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. Đánh số trang (4 điểm)

Một cuốn sách có n trang, được đánh số 1, 2, 3, …, n.

Yêu cầu: Tính tổng số chữ số cần dùng để in số trang của cả cuốn sách.

Dữ liệu vào: Từ file văn bản DANHSO.INP gồm một số nguyên dương n.

Kết quả: Ghi ra file văn bản DANHSO.OUT một số nguyên là tổng số chữ số.

Ví dụ:

DANHSO.INP	DANHSO.OUT	Giải thích
`125`	`267`	9 trang có 1 chữ số, 90 trang có 2 chữ số, 26 trang có 3 chữ số: 9 + 180 + 78 = 267.

Ràng buộc:

Có 50% số test với n ≤ 10⁶.
Có 50% số test với n ≤ 10¹⁷.

Bài 2. Mật mã Vigenère (5 điểm)

Mật mã Vigenère dùng một từ khóa gồm các chữ cái in thường. Chữ cái a ứng với độ dịch 0, b ứng với 1, …, z ứng với 25. Để mã hóa một văn bản, lần lượt ghép mỗi chữ cái của văn bản với chữ cái tiếp theo của từ khóa (hết từ khóa thì quay lại từ đầu), rồi dịch chữ cái đó đi về phía sau trong bảng chữ cái theo độ dịch tương ứng (sau z quay lại a). Chữ in hoa vẫn là chữ in hoa, chữ in thường vẫn là chữ in thường. Các kí tự không phải chữ cái giữ nguyên và không dùng đến từ khóa. Giải mã là dịch ngược lại.

Yêu cầu: Cho từ khóa, một văn bản cần mã hóa và một văn bản cần giải mã, hãy thực hiện hai việc đó.

Dữ liệu vào: Từ file văn bản MAHOA.INP gồm ba dòng: từ khóa (không quá 100 chữ cái in thường); văn bản cần mã hóa; văn bản cần giải mã. Mỗi văn bản dài không quá 10⁵ kí tự, gồm chữ cái, chữ số, dấu câu và dấu cách.

Kết quả: Ghi ra file văn bản MAHOA.OUT gồm hai dòng: văn bản sau khi mã hóa và văn bản sau khi giải mã.

Ví dụ:

MAHOA.INP	MAHOA.OUT	Giải thích
`bai` `Hoc Tin, vui lam!` `Dhcd tpj twu!`	`Iok Uiv, wuq mau!` `Chuc thi tot!`	H dịch 1 thành I, o dịch 0 giữ nguyên o, c dịch 8 thành k, T dịch 1 thành U, …

Ràng buộc:

Có 40% số test với từ khóa chỉ có 1 chữ cái.
Có 60% số test với từ khóa có tới 100 chữ cái.

Bài 3. Chuỗi ngày đạt chỉ tiêu (5 điểm)

Một cửa hàng ghi lại doanh thu n ngày liên tiếp a₁, a₂, …, a_n (có thể âm nếu ngày đó bị lỗ). Chỉ tiêu là doanh thu trung bình mỗi ngày ít nhất bằng K.

Yêu cầu: Tìm độ dài lớn nhất của một chuỗi ngày liên tiếp có doanh thu trung bình không nhỏ hơn K.

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

Dòng đầu tiên chứa hai số nguyên n và K (n ≥ 1, |K| ≤ 10⁹).
Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (|a_i| ≤ 10⁹).

Kết quả: Ghi ra file văn bản DOANTB.OUT một số nguyên là độ dài lớn nhất (ghi 0 nếu không có ngày nào đạt chỉ tiêu).

Ví dụ:

DOANTB.INP	DOANTB.OUT	Giải thích
`7 5` `3 8 2 9 1 1 6`	`4`	Bốn ngày đầu có trung bình 22 / 4 = 5,5.

Ràng buộc:

Có 40% số test với n ≤ 2000.
Có 60% số test với n ≤ 2 × 10⁵.

Bài 4. Phá tường (6 điểm)

Một mê cung là lưới m × n ô: ô . là đường đi, ô # là tường, ô S là vị trí xuất phát, ô T là lối ra. Mỗi bước có thể đi sang một ô chung cạnh. Bạn có một chiếc búa dùng được đúng một lần để phá một bức tường: bước vào ô tường đó cũng tính là một bước.

Yêu cầu: Tìm số bước ít nhất để đi từ S đến T (có thể không cần dùng búa).

Dữ liệu vào: Từ file văn bản PHATUONG.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ự thuộc .#ST. Lưới có đúng một ô S và một ô T.

Kết quả: Ghi ra file văn bản PHATUONG.OUT một số nguyên là số bước ít nhất, hoặc -1 nếu không thể đến T.

Ví dụ:

PHATUONG.INP	PHATUONG.OUT	Giải thích
`3 5` `S.#..` `..#..` `..#.T`	`6`	Phá bức tường ở hàng 1, cột 3 rồi đi tiếp sang phải và xuống.

Ràng buộc:

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

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