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

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

ĐỀ SỐ 10 Thời gian làm bài: 150 phút
3 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	Chuẩn hóa họ tên	`CHUANHOA.*`	`CHUANHOA.INP`	`CHUANHOA.OUT`	6
2	Ma trận xoắn ốc	`XOANOC.*`	`XOANOC.INP`	`XOANOC.OUT`	6
3	Số phong phú	`PHONGPHU.*`	`PHONGPHU.INP`	`PHONGPHU.OUT`	8

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. Chuẩn hóa họ tên (6 điểm)

Khi nhập danh sách lớp, các bạn gõ họ tên không dấu rất tùy tiện: lẫn chữ hoa chữ thường, thừa dấu cách ở đầu, cuối và giữa các từ (ví dụ nguyEn VaN bINh).

Yêu cầu: Cho một họ tên, hãy in ra:

Họ tên viết in hoa toàn bộ, các từ cách nhau đúng một dấu cách.
Họ tên chuẩn: chữ cái đầu mỗi từ in hoa, các chữ còn lại in thường, các từ cách nhau đúng một dấu cách.
Tên viết tắt: các chữ cái đầu của mỗi từ, in hoa, viết liền nhau.

Dữ liệu vào: Từ file văn bản CHUANHOA.INP gồm một dòng chứa họ tên (chỉ gồm chữ cái tiếng Anh và dấu cách, có ít nhất một từ).

Kết quả: Ghi ra file văn bản CHUANHOA.OUT gồm ba dòng theo thứ tự trên.

Ví dụ:

CHUANHOA.INP	CHUANHOA.OUT
`nguyEn VaN bINh`	`NGUYEN VAN BINH` `Nguyen Van Binh` `NVB`

Ràng buộc: Độ dài dòng không quá 1000 kí tự.

Bài 2. Ma trận xoắn ốc (6 điểm)

Điền các số 1, 2, …, n² vào bảng vuông n × n theo hình xoắn ốc cùng chiều kim đồng hồ, bắt đầu từ ô trên cùng bên trái. Ví dụ với n = 4:

	Cột 1	Cột 2	Cột 3	Cột 4
Hàng 1	1	2	3	4
Hàng 2	12	13	14	5
Hàng 3	11	16	15	6
Hàng 4	10	9	8	7

Yêu cầu: Trả lời q câu hỏi, mỗi câu hỏi cho biết số được điền ở ô hàng r, cột c.

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

Dòng đầu tiên chứa hai số nguyên dương n và q.
q dòng tiếp theo, mỗi dòng chứa hai số nguyên r, c (1 ≤ r, c ≤ n).

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

Ví dụ:

XOANOC.INP	XOANOC.OUT
`4 4` `1 1` `2 1` `3 3` `2 2`	`1` `12` `15` `13`

Ràng buộc:

Có 40% số test với n ≤ 100, q ≤ 100.
Có 60% số test với n ≤ 10⁹, q ≤ 10⁵.

Bài 3. Số phong phú (8 điểm)

Số phong phú là số nguyên dương có tổng các ước dương (không kể chính nó) lớn hơn nó. Ví dụ 12 là số phong phú vì 1 + 2 + 3 + 4 + 6 = 16 > 12; còn 10 không phải vì 1 + 2 + 5 = 8.

Yêu cầu: Cho q đoạn [a, b], với mỗi đoạn hãy đếm số lượng số phong phú thuộc đoạn đó.

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

Dòng đầu tiên chứa số nguyên dương q.
q dòng tiếp theo, mỗi dòng chứa hai số nguyên a, b (1 ≤ a ≤ b).

Kết quả: Ghi ra file văn bản PHONGPHU.OUT gồm q dòng, dòng thứ i là số lượng số phong phú trong đoạn thứ i.

Ví dụ:

PHONGPHU.INP	PHONGPHU.OUT	Giải thích
`2` `12 20` `1 11`	`3` `0`	Trong [12, 20] có 12, 18, 20. Số phong phú nhỏ nhất là 12.

Ràng buộc:

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

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