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

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

ĐỀ SỐ 11 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	Cộng trừ số lớn	`CONGSO.*`	`CONGSO.INP`	`CONGSO.OUT`	4
2	Viết ngược	`DAOTU.*`	`DAOTU.INP`	`DAOTU.OUT`	5
3	Số k nhỏ nhất	`KNHONHAT.*`	`KNHONHAT.INP`	`KNHONHAT.OUT`	5
4	Xếp hàng chụp ảnh	`DEMTRUOC.*`	`DEMTRUOC.INP`	`DEMTRUOC.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. Cộng trừ số lớn (4 điểm)

Cho hai số nguyên dương a và b, có thể rất lớn.

Yêu cầu: Tính tổng a + b và hiệu |a − b| (giá trị tuyệt đối của hiệu).

Dữ liệu vào: Từ file văn bản CONGSO.INP gồm một dòng chứa hai số nguyên dương a, b (không có chữ số 0 ở đầu), cách nhau một dấu cách.

Kết quả: Ghi ra file văn bản CONGSO.OUT gồm hai dòng: a + b và |a − b|.

Ví dụ:

CONGSO.INP	CONGSO.OUT
`987654321987654321 123456789`	`987654322111111110` `987654321864197532`

Ràng buộc:

Có 50% số test với a, b ≤ 10¹⁸.
Có 50% số test với a, b có tới 10⁵ chữ số.

Bài 2. Viết ngược (5 điểm)

Cho một dòng văn bản tiếng Việt không dấu, trong đó các từ có thể bị cách nhau bởi nhiều dấu cách và có thể dính dấu câu (ví dụ nay, hay khong?). Mỗi từ là một dãy kí tự khác dấu cách đứng liền nhau.

Yêu cầu:

Chuẩn hóa dòng văn bản: bỏ các dấu cách thừa, các từ cách nhau đúng một dấu cách.
Viết ngược từng từ: đảo ngược thứ tự các chữ cái và chữ số trong từ, còn các dấu câu giữ nguyên vị trí. Thứ tự các từ không đổi.

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

Kết quả: Ghi ra file văn bản DAOTU.OUT gồm hai dòng: dòng đã chuẩn hóa và dòng đã viết ngược các từ (các từ cách nhau đúng một dấu cách).

Ví dụ:

DAOTU.INP	DAOTU.OUT
`Chieu nay, Lan co di hoc khong?`	`Chieu nay, Lan co di hoc khong?` `ueihC yan, naL oc id coh gnohk?`

Ràng buộc: Gọi L là độ dài dòng văn bản.

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

Bài 3. Số k nhỏ nhất (5 điểm)

Cho hai số nguyên dương m và n.

Yêu cầu: Tìm số tự nhiên k nhỏ nhất (k ≥ 0) sao cho (k + m) chia hết cho n và (k + n) chia hết cho m. Có T câu hỏi như vậy.

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

Dòng đầu tiên chứa số nguyên dương T.
T dòng tiếp theo, mỗi dòng chứa hai số nguyên dương m, n.

Kết quả: Ghi ra file văn bản KNHONHAT.OUT gồm T dòng, mỗi dòng là số k tìm được.

Ví dụ:

KNHONHAT.INP	KNHONHAT.OUT	Giải thích
`3` `12 20` `5 5` `4 6`	`28` `0` `2`	28 + 12 = 40 chia hết cho 20 và 28 + 20 = 48 chia hết cho 12.

Ràng buộc:

Có 40% số test với T ≤ 10, m, n ≤ 1000.
Có 60% số test với T ≤ 10⁵, m, n ≤ 10⁹.

Bài 4. Xếp hàng chụp ảnh (6 điểm)

Có n bạn học sinh đứng thành một hàng để chụp ảnh, bạn thứ i cao a_i cm. Nhiếp ảnh gia muốn biết, với mỗi bạn, có bao nhiêu bạn đứng phía trước (có chỉ số nhỏ hơn) mà thấp hơn hẳn bạn đó.

Yêu cầu: Với mỗi i, tính b_i là số lượng chỉ số j < i có a_j < a_i.

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

Dòng đầu tiên chứa số nguyên dương n.
Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁵).

Kết quả: Ghi ra file văn bản DEMTRUOC.OUT một dòng gồm n số b₁, b₂, …, b_n.

Ví dụ:

DEMTRUOC.INP	DEMTRUOC.OUT	Giải thích
`6` `150 145 160 150 170 140`	`0 0 2 1 4 0`	Trước bạn cao 170 có 4 bạn thấp hơn; trước bạn thứ tư (150) chỉ có bạn cao 145 thấp hơn hẳn.

Ràng buộc:

Có 40% số test với n ≤ 2000.
Có 60% số test với n ≤ 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