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

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

ĐỀ SỐ 25 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	ƯCLN và BCNN của dãy	`UCLN3.*`	`UCLN3.INP`	`UCLN3.OUT`	4
2	Cặp nghịch thế	`NGHICHTHE.*`	`NGHICHTHE.INP`	`NGHICHTHE.OUT`	5
3	Đặt trạm phát sóng	`TRAMPHAT.*`	`TRAMPHAT.INP`	`TRAMPHAT.OUT`	5
4	Đi xuống núi	`TONGMAXLUOI.*`	`TONGMAXLUOI.INP`	`TONGMAXLUOI.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. ƯCLN và BCNN của dãy (4 điểm)

Yêu cầu: Cho dãy n số nguyên dương a₁, a₂, …, a_n, hãy tìm ước chung lớn nhất và bội chung nhỏ nhất của cả dãy.

Dữ liệu vào: Từ file văn bản UCLN3.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.

Dữ liệu bảo đảm BCNN của cả dãy không vượt quá 10¹⁸.

Kết quả: Ghi ra file văn bản UCLN3.OUT gồm hai dòng: ƯCLN và BCNN của dãy.

Ví dụ:

UCLN3.INP	UCLN3.OUT
`4` `12 18 30 8`	`2` `360`

Ràng buộc:

Có 50% số test với n ≤ 10, a_i ≤ 1000.
Có 50% số test với n ≤ 10⁵, a_i ≤ 10⁹.

Bài 2. Cặp nghịch thế (5 điểm)

Trong dãy a₁, a₂, …, a_n, cặp chỉ số (i, j) được gọi là nghịch thế nếu i nhỏ hơn j nhưng a_i lớn hơn a_j. Số cặp nghịch thế cho biết dãy “lộn xộn” đến mức nào so với dãy đã sắp xếp tăng dần.

Yêu cầu: Đếm số cặp nghịch thế của dãy.

Dữ liệu vào: Từ file văn bản NGHICHTHE.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 NGHICHTHE.OUT một số nguyên là số cặp nghịch thế.

Ví dụ:

NGHICHTHE.INP	NGHICHTHE.OUT	Giải thích
`5` `3 1 4 1 5`	`3`	Các cặp (3, 1), (3, 1), (4, 1).

Ràng buộc:

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

Bài 3. Đặt trạm phát sóng (5 điểm)

Dọc một con đường có n vị trí có thể đặt trạm phát sóng, vị trí thứ i cách đầu đường x_i mét (có thể có nhiều vị trí trùng nhau). Nhà mạng cần đặt đúng k trạm tại k vị trí khác nhau trong số đó. Để các trạm không gây nhiễu cho nhau, khoảng cách giữa hai trạm gần nhau nhất phải càng lớn càng tốt.

Yêu cầu: Tìm giá trị lớn nhất có thể của khoảng cách giữa hai trạm gần nhau nhất.

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

Dòng đầu tiên chứa hai số nguyên n, k (2 ≤ k ≤ n).
Dòng thứ hai chứa n số nguyên x₁, x₂, …, x_n (0 ≤ x_i ≤ 10⁹).

Kết quả: Ghi ra file văn bản TRAMPHAT.OUT một số nguyên là khoảng cách tìm được.

Ví dụ:

TRAMPHAT.INP	TRAMPHAT.OUT	Giải thích
`5 3` `1 2 8 4 9`	`3`	Đặt trạm ở vị trí 1, 4, 8 (hoặc 1, 4, 9).

Ràng buộc:

Có 30% số test với n ≤ 15.
Có 70% số test với n ≤ 5 × 10⁴.

Bài 4. Đi xuống núi (6 điểm)

Sườn núi được chia thành lưới m hàng, n cột; ô ở hàng i, cột j ghi số điểm a_ij (có thể âm). Một nhà leo núi xuất phát từ một ô bất kì ở hàng 1 và đi xuống hàng m. Từ ô (i, j), mỗi bước chỉ được đi xuống một trong các ô (i + 1, j − 1), (i + 1, j), (i + 1, j + 1) (nếu ô đó nằm trong lưới).

Yêu cầu: Tìm tổng điểm lớn nhất của các ô trên đường đi (tính cả ô xuất phát và ô kết thúc).

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

Dòng đầu tiên chứa hai số nguyên dương m, n.
m dòng tiếp theo, mỗi dòng chứa n số nguyên có giá trị tuyệt đối không quá 10⁹.

Kết quả: Ghi ra file văn bản TONGMAXLUOI.OUT một số nguyên là tổng điểm lớn nhất.

Ví dụ:

TONGMAXLUOI.INP	TONGMAXLUOI.OUT	Giải thích
`4 4` `1 2 3 4` `5 -9 6 1` `2 8 -1 3` `4 1 7 -2`	`25`	Đi qua các ô có điểm 4, 6, 8, 7.

Ràng buộc:

Có 30% số test với m, n ≤ 8.
Có 70% số test với m, n ≤ 500.

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