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

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

ĐỀ SỐ 16 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	Tuổi cha và con	`TUOICHA.*`	`TUOICHA.INP`	`TUOICHA.OUT`	4
2	Đảo thứ tự từ	`DAOCAU.*`	`DAOCAU.INP`	`DAOCAU.OUT`	5
3	Số nguyên tố lớn nhất	`NTLONNHAT.*`	`NTLONNHAT.INP`	`NTLONNHAT.OUT`	5
4	Thu hoạch trên thửa ruộng	`TONGHCN.*`	`TONGHCN.INP`	`TONGHCN.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. Tuổi cha và con (4 điểm)

Hiện nay cha F tuổi, con S tuổi (S < F; con S = 0 tuổi nghĩa là vừa mới sinh).

Yêu cầu: Cho biết vào thời điểm nào (trước đây, hiện tại hay sau này) tuổi cha gấp đúng k lần tuổi con. Thời điểm đó phải cách hiện tại một số nguyên năm và khi đó người con đã ít nhất 1 tuổi.

Dữ liệu vào: Từ file văn bản TUOICHA.INP gồm một dòng chứa ba số nguyên F, S, k (k ≥ 2).

Kết quả: Ghi ra file văn bản TUOICHA.OUT một trong các dạng sau:

SAU t: sau t năm nữa;
TRUOC t: cách đây t năm;
HIEN TAI: ngay năm nay;
KHONG: không có thời điểm nào như vậy.

Ví dụ:

TUOICHA.INP	TUOICHA.OUT	Giải thích
`40 10 2`	`SAU 20`	20 năm nữa cha 60 tuổi, con 30 tuổi.
`31 11 3`	`TRUOC 1`	Năm ngoái cha 30 tuổi, con 10 tuổi.
`30 10 4`	`KHONG`	Cần 30 + t = 4(10 + t), không có t nguyên.

Ràng buộc:

Có 50% số test với S < F ≤ 200, k ≤ 10.
Có 50% số test với S < F ≤ 10⁹, k ≤ 10⁹.

Bài 2. Đảo thứ tự từ (5 điểm)

Cho một câu gồm các từ ngăn cách bởi một hoặc nhiều dấu cách. Mỗi từ là một dãy kí tự khác dấu cách đứng liền nhau.

Yêu cầu: Đếm số từ của câu và viết lại câu theo thứ tự các từ đảo ngược (từ cuối lên đầu), các từ cách nhau đúng một dấu cách.

Dữ liệu vào: Từ file văn bản DAOCAU.INP gồm một dòng chứa câu (có ít nhất một từ).

Kết quả: Ghi ra file văn bản DAOCAU.OUT gồm hai dòng: số từ và câu sau khi đảo.

Ví dụ:

DAOCAU.INP	DAOCAU.OUT
`choi di xe dap`	`4` `dap xe di choi`

Ràng buộc: Gọi L là độ dài dòng.

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

Bài 3. Số nguyên tố lớn nhất (5 điểm)

Yêu cầu: Cho q số nguyên a (a ≥ 2). Với mỗi số, hãy tìm số nguyên tố lớn nhất không vượt quá a và đếm xem có bao nhiêu số nguyên tố không vượt quá a.

Dữ liệu vào: Từ file văn bản NTLONNHAT.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 một số nguyên a.

Kết quả: Ghi ra file văn bản NTLONNHAT.OUT gồm q dòng, mỗi dòng hai số: số nguyên tố lớn nhất không vượt quá a và số lượng số nguyên tố không vượt quá a.

Ví dụ:

NTLONNHAT.INP	NTLONNHAT.OUT	Giải thích
`3` `10` `45` `2`	`7 4` `43 14` `2 1`	Các số nguyên tố không vượt quá 10 là 2, 3, 5, 7.

Ràng buộc:

Có 40% số test với q ≤ 100, a ≤ 10⁴.
Có 60% số test với q ≤ 10⁵, a ≤ 5 × 10⁶.

Bài 4. Thu hoạch trên thửa ruộng (6 điểm)

Một cánh đồng hình chữ nhật được chia thành lưới m hàng, n cột; ô ở hàng i, cột j có sản lượng a_ij (có thể âm nếu ô đó bị thiệt hại, phải bù lỗ). Người ta cần trả lời q câu hỏi, mỗi câu hỏi là tổng sản lượng của một thửa ruộng hình chữ nhật con.

Yêu cầu: Với mỗi câu hỏi (x₁, y₁, x₂, y₂), tính tổng các ô từ hàng x₁ đến hàng x₂, từ cột y₁ đến cột y₂.

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

Dòng đầu tiên chứa ba số nguyên dương m, n, q.
m dòng tiếp theo, mỗi dòng chứa n số nguyên (|a_ij| ≤ 10⁹).
q dòng tiếp theo, mỗi dòng chứa bốn số nguyên x₁, y₁, x₂, y₂ (1 ≤ x₁ ≤ x₂ ≤ m, 1 ≤ y₁ ≤ y₂ ≤ n).

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

Ví dụ:

TONGHCN.INP	TONGHCN.OUT	Giải thích
`3 4 2` `1 2 3 4` `5 6 7 8` `9 10 11 12` `2 2 3 3` `1 1 3 4`	`34` `78`	6 + 7 + 10 + 11 = 34; tổng cả bảng là 78.

Ràng buộc:

Có 40% số test với m, n ≤ 50, q ≤ 100.
Có 60% số test với m, n ≤ 500, q ≤ 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