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

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

ĐỀ SỐ 24 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	Hai tấm thảm	`HCN.*`	`HCN.INP`	`HCN.OUT`	4
2	Tòa nhà cao hơn gần nhất	`GANLONHON.*`	`GANLONHON.INP`	`GANLONHON.OUT`	5
3	Nhiệt độ cao nhất theo tuần	`CUASO.*`	`CUASO.INP`	`CUASO.OUT`	5
4	Xâu con chung dài nhất	`LCS.*`	`LCS.INP`	`LCS.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. Hai tấm thảm (4 điểm)

Trên sàn nhà (coi như mặt phẳng tọa độ) có hai tấm thảm hình chữ nhật với các cạnh song song với các trục tọa độ. Tấm thứ nhất có góc dưới trái (x₁, y₁) và góc trên phải (x₂, y₂); tấm thứ hai có góc dưới trái (u₁, v₁) và góc trên phải (u₂, v₂).

Yêu cầu: Tính diện tích phần hai tấm thảm chồng lên nhau và diện tích phần sàn được phủ (bởi ít nhất một tấm thảm).

Dữ liệu vào: Từ file văn bản HCN.INP gồm một dòng chứa tám số nguyên x₁, y₁, x₂, y₂, u₁, v₁, u₂, v₂ (x₁ nhỏ hơn x₂, y₁ nhỏ hơn y₂, u₁ nhỏ hơn u₂, v₁ nhỏ hơn v₂).

Kết quả: Ghi ra file văn bản HCN.OUT gồm hai dòng: diện tích phần chồng lên nhau và diện tích phần được phủ.

Ví dụ:

HCN.INP	HCN.OUT	Giải thích
`0 0 4 3 2 1 6 5`	`4` `24`	Phần chung là hình chữ nhật từ (2, 1) đến (4, 3). 12 + 16 − 4 = 24.

Ràng buộc:

Có 50% số test với các tọa độ có giá trị tuyệt đối không quá 50.
Có 50% số test với các tọa độ có giá trị tuyệt đối không quá 10⁹.

Bài 2. Tòa nhà cao hơn gần nhất (5 điểm)

Trên một con phố có n tòa nhà xếp thành hàng từ trái sang phải, tòa thứ i cao a_i mét. Từ nóc mỗi tòa nhà, người ta nhìn sang phải và muốn biết tòa nhà đầu tiên cao hơn hẳn nó.

Yêu cầu: Với mỗi tòa nhà, cho biết chiều cao của tòa nhà gần nhất bên phải cao hơn nó, hoặc −1 nếu không có.

Dữ liệu vào: Từ file văn bản GANLONHON.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 GANLONHON.OUT một dòng gồm n số là đáp án cho từng tòa nhà.

Ví dụ:

GANLONHON.INP	GANLONHON.OUT
`7` `5 3 8 1 4 9 2`	`8 8 9 4 9 -1 -1`

Ràng buộc:

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

Bài 3. Nhiệt độ cao nhất theo tuần (5 điểm)

Trạm khí tượng ghi lại nhiệt độ của n ngày liên tiếp: a₁, a₂, …, a_n. Với mỗi “tuần” gồm k ngày liên tiếp (ngày 1 đến ngày k, ngày 2 đến ngày k + 1, …, ngày n − k + 1 đến ngày n), cần biết nhiệt độ cao nhất.

Yêu cầu: In ra nhiệt độ cao nhất của từng đoạn k ngày liên tiếp.

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

Dòng đầu tiên chứa hai số nguyên dương n và k (k ≤ n).
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 CUASO.OUT một dòng gồm n − k + 1 số.

Ví dụ:

CUASO.INP	CUASO.OUT
`8 3` `1 3 -1 -3 5 3 6 7`	`3 3 5 5 6 7`

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âu con chung dài nhất (6 điểm)

Một xâu con (không cần liên tiếp) của xâu S nhận được bằng cách xóa đi một số kí tự của S (có thể không xóa) và giữ nguyên thứ tự các kí tự còn lại. Ví dụ bcb là xâu con của abcbdab.

Yêu cầu: Cho hai xâu A và B, tìm độ dài của xâu dài nhất vừa là xâu con của A vừa là xâu con của B.

Dữ liệu vào: Từ file văn bản LCS.INP gồm hai dòng lần lượt chứa hai xâu A, B (chỉ gồm chữ cái in thường).

Kết quả: Ghi ra file văn bản LCS.OUT một số nguyên là độ dài tìm được.

Ví dụ:

LCS.INP	LCS.OUT	Giải thích
`abcbdab` `bdcaba`	`4`	Ví dụ xâu `bcba` hoặc `bdab`.

Ràng buộc:

Có 30% số test với độ dài mỗi xâu không quá 12.
Có 70% số test với độ dài mỗi xâu không quá 1000.

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