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

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

ĐỀ SỐ 19 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	Đổi tiền	`DOITIEN.*`	`DOITIEN.INP`	`DOITIEN.OUT`	4
2	Xâu con đối xứng dài nhất	`XAUDX.*`	`XAUDX.INP`	`XAUDX.OUT`	5
3	Đếm đoạn có tổng bằng K	`DEMDOAN.*`	`DEMDOAN.INP`	`DEMDOAN.OUT`	5
4	Xếp lịch phòng họp	`LICHHOP.*`	`LICHHOP.INP`	`LICHHOP.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. Đổi tiền (4 điểm)

Ngân hàng có các tờ tiền mệnh giá 500 000, 200 000, 100 000, 50 000, 20 000, 10 000, 5 000, 2 000 và 1 000 đồng (mỗi loại có đủ nhiều tờ).

Yêu cầu: Đổi N đồng thành ít tờ tiền nhất, cho biết số tờ và số tờ mỗi mệnh giá.

Dữ liệu vào: Từ file văn bản DOITIEN.INP gồm một số nguyên N (N chia hết cho 1000, N ≥ 1000).

Kết quả: Ghi ra file văn bản DOITIEN.OUT: dòng thứ nhất ghi tổng số tờ; các dòng tiếp theo, mỗi dòng ghi một mệnh giá được dùng và số tờ của mệnh giá đó, theo thứ tự mệnh giá giảm dần.

Ví dụ:

DOITIEN.INP	DOITIEN.OUT
`888000`	`9` `500000 1` `200000 1` `100000 1` `50000 1` `20000 1` `10000 1` `5000 1` `2000 1` `1000 1`

Ràng buộc:

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

Bài 2. Xâu con đối xứng dài nhất (5 điểm)

Yêu cầu: Cho xâu S gồm các chữ cái in thường, tìm xâu con liên tiếp dài nhất của S là xâu đối xứng. Nếu có nhiều xâu như vậy thì chọn xâu xuất hiện sớm nhất.

Dữ liệu vào: Từ file văn bản XAUDX.INP gồm một dòng chứa xâu S.

Kết quả: Ghi ra file văn bản XAUDX.OUT gồm hai dòng: độ dài và nội dung xâu con tìm được.

Ví dụ:

XAUDX.INP	XAUDX.OUT	Giải thích
`babad`	`3` `bab`	“aba” cũng dài 3 nhưng xuất hiện sau.
`cbbdabccbad`	`8` `dabccbad`

Ràng buộc: Gọi n là độ dài xâu S.

Có 40% số test với n ≤ 100.
Có 60% số test với n ≤ 2000.

Bài 3. Đếm đoạn có tổng bằng K (5 điểm)

Cho dãy n số nguyên a₁, a₂, …, a_n (có thể âm) và số nguyên K.

Yêu cầu: Đếm số đoạn con liên tiếp (gồm ít nhất một phần tử) có tổng bằng K.

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

Dòng đầu tiên chứa hai số nguyên n và K (|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 DEMDOAN.OUT một số nguyên là số đoạn tìm được.

Ví dụ:

DEMDOAN.INP	DEMDOAN.OUT	Giải thích
`6 5` `2 3 -1 1 5 0`	`6`	Các đoạn (2, 3), (2, 3, −1, 1), (−1, 1, 5), (−1, 1, 5, 0), (5), (5, 0).

Ràng buộc:

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

Bài 4. Xếp lịch phòng họp (6 điểm)

Nhà trường nhận được n đăng kí sử dụng phòng họp, đăng kí thứ i bắt đầu lúc s_i và kết thúc lúc e_i (s_i nhỏ hơn e_i). Phòng họp chỉ phục vụ một cuộc họp tại một thời điểm, nhưng một cuộc họp có thể bắt đầu đúng lúc cuộc họp trước kết thúc.

Yêu cầu: Tìm số cuộc họp nhiều nhất có thể xếp vào phòng.

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

Dòng đầu tiên chứa số nguyên dương n.
n dòng tiếp theo, mỗi dòng chứa hai số nguyên s_i, e_i (0 ≤ s_i, e_i ≤ 10⁹).

Kết quả: Ghi ra file văn bản LICHHOP.OUT một số nguyên là số cuộc họp nhiều nhất.

Ví dụ:

LICHHOP.INP	LICHHOP.OUT	Giải thích
`5` `1 4` `3 5` `0 6` `5 7` `8 9`	`3`	Chọn (1, 4), (5, 7), (8, 9).

Ràng buộc:

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