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

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

ĐỀ SỐ 26 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	Chia kẹo	`CHIAQUA.*`	`CHIAQUA.INP`	`CHIAQUA.OUT`	3
2	Phép XOR trên đoạn	`XORDAY.*`	`XORDAY.INP`	`XORDAY.OUT`	5
3	Thoát khỏi mê cung	`MECUNG.*`	`MECUNG.INP`	`MECUNG.OUT`	6
4	Đếm đảo	`DAO.*`	`DAO.INP`	`DAO.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. Chia kẹo (3 điểm)

Cô giáo có n viên kẹo và muốn chia đều cho k bạn (mỗi bạn nhận số kẹo như nhau, nhiều nhất có thể).

Yêu cầu: Cho biết mỗi bạn được bao nhiêu viên, cô còn thừa bao nhiêu viên, và cô cần mua thêm ít nhất bao nhiêu viên để chia đều mà không thừa viên nào.

Dữ liệu vào: Từ file văn bản CHIAQUA.INP gồm một dòng chứa hai số nguyên dương n, k.

Kết quả: Ghi ra file văn bản CHIAQUA.OUT gồm hai dòng: dòng thứ nhất ghi số kẹo mỗi bạn nhận và số kẹo còn thừa; dòng thứ hai ghi số kẹo cần mua thêm.

Ví dụ:

CHIAQUA.INP	CHIAQUA.OUT	Giải thích
`23 5`	`4 3` `2`	23 = 5 × 4 + 3; mua thêm 2 viên thì có 25 viên, chia đều mỗi bạn 5 viên.

Ràng buộc:

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

Bài 2. Phép XOR trên đoạn (5 điểm)

Phép XOR (kí hiệu ⊕; trong Python và C++ viết là ^) của hai số nguyên không âm là phép toán trên từng bit: bit kết quả bằng 1 khi hai bit tương ứng khác nhau. Ví dụ 5 ⊕ 3 = 101₂ ⊕ 011₂ = 110₂ = 6.

Yêu cầu: Cho dãy n số nguyên không âm a₁, a₂, …, a_n và q câu hỏi. Mỗi câu hỏi (l, r) hỏi giá trị a_l ⊕ a_l+1 ⊕ … ⊕ a_r.

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

Dòng đầu tiên chứa hai số nguyên dương n và q.
Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (0 ≤ a_i ≤ 10⁹).
q dòng tiếp theo, mỗi dòng chứa hai số nguyên l, r (1 ≤ l ≤ r ≤ n).

Kết quả: Ghi ra file văn bản XORDAY.OUT gồm q dòng là câu trả lời cho các câu hỏi.

Ví dụ:

XORDAY.INP	XORDAY.OUT	Giải thích
`5 3` `3 5 6 2 7` `1 3` `2 5` `4 4`	`0` `6` `2`	3 ⊕ 5 ⊕ 6 = 0.

Ràng buộc:

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

Bài 3. Thoát khỏi mê cung (6 điểm)

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 (lên, xuống, trái, phải) không phải tường.

Yêu cầu: Tìm số bước ít nhất để đi từ S đến T.

Dữ liệu vào: Từ file văn bản MECUNG.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 MECUNG.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ụ:

MECUNG.INP	MECUNG.OUT
`4 5` `S.#..` `.##.#` `...#T` `#....`	`8`

Ràng buộc:

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

Bài 4. Đếm đảo (6 điểm)

Bản đồ một vùng biển là lưới m × n ô: 1 là đất, 0 là nước. Một hòn đảo là một nhóm các ô đất liên thông với nhau qua các cạnh chung (không tính đường chéo). Diện tích hòn đảo là số ô của nó.

Yêu cầu: Đếm số hòn đảo và tìm diện tích của hòn đảo lớn nhất.

Dữ liệu vào: Từ file văn bản DAO.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ự 0 hoặc 1.

Kết quả: Ghi ra file văn bản DAO.OUT hai số: số hòn đảo và diện tích hòn đảo lớn nhất (bằng 0 nếu không có đảo nào).

Ví dụ:

DAO.INP	DAO.OUT	Giải thích
`4 5` `11000` `11011` `00010` `10111`	`3 6`	Đảo 4 ô ở góc trên trái, đảo 6 ô bên phải và đảo 1 ô ở góc dưới trái.

Ràng buộc:

Có 30% số test với m, n ≤ 50.
Có 70% 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