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

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

ĐỀ SỐ 21 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	Xếp loại học lực	`DIEMTB.*`	`DIEMTB.INP`	`DIEMTB.OUT`	4
2	Hàng, cột và chữ thập	`BANGSO.*`	`BANGSO.INP`	`BANGSO.OUT`	5
3	Đoạn chia hết	`DOANCHIA.*`	`DOANCHIA.INP`	`DOANCHIA.OUT`	5
4	Ba lô dã ngoại	`CAITUI.*`	`CAITUI.INP`	`CAITUI.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. Xếp loại học lực (4 điểm)

Mỗi học sinh có k điểm môn học (số nguyên từ 0 đến 10). Gọi TB là điểm trung bình các môn, m là điểm môn thấp nhất. Học sinh được xếp loại:

Giỏi nếu TB ≥ 8 và m ≥ 6;
ngược lại, Khá nếu TB ≥ 6,5 và m ≥ 5;
ngược lại, Trung bình nếu TB ≥ 5 và m ≥ 3,5;
còn lại là Yếu.

Yêu cầu: Đếm số học sinh xếp loại Giỏi, Khá, Trung bình, Yếu.

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

Dòng đầu tiên chứa hai số nguyên dương n (số học sinh) và k (số môn).
n dòng tiếp theo, mỗi dòng chứa k điểm của một học sinh.

Kết quả: Ghi ra file văn bản DIEMTB.OUT bốn số: số học sinh Giỏi, Khá, Trung bình, Yếu.

Ví dụ:

DIEMTB.INP	DIEMTB.OUT	Giải thích
`5 3` `9 8 7` `7 6 7` `6 5 6` `10 10 3` `8 8 6`	`1 2 1 1`	Bạn thứ năm có TB ≈ 7,33 nên chỉ xếp loại Khá. Bạn thứ tư có TB ≈ 7,67 nhưng có môn 3 điểm nên xếp loại Yếu.

Ràng buộc: n ≤ 10⁵, k ≤ 10.

Bài 2. Hàng, cột và chữ thập (5 điểm)

Cho bảng số nguyên m hàng, n cột. Chữ thập tại ô (i, j) gồm toàn bộ hàng i và toàn bộ cột j (ô (i, j) chỉ tính một lần).

Yêu cầu:

Tìm hàng có tổng lớn nhất.
Tìm cột có tổng lớn nhất.
Tìm ô (i, j) mà chữ thập tại đó có tổng lớn nhất.

Nếu có nhiều đáp án thì chọn hàng (cột) có chỉ số nhỏ nhất; với câu 3 chọn i nhỏ nhất, rồi đến j nhỏ nhất.

Dữ liệu vào: Từ file văn bản BANGSO.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 BANGSO.OUT gồm ba dòng: chỉ số hàng và tổng của nó; chỉ số cột và tổng của nó; chỉ số hàng, chỉ số cột của ô và tổng chữ thập tại đó.

Ví dụ:

BANGSO.INP	BANGSO.OUT	Giải thích
`3 4` `1 2 3 4` `5 -6 7 8` `1 1 1 1`	`2 14` `4 13` `1 4 19`	Chữ thập tại (1, 4) và (2, 4) đều có tổng 19, chọn hàng nhỏ hơn.

Ràng buộc:

Có 50% số test với m, n ≤ 50.
Có 50% số test với m, n ≤ 700.

Bài 3. Đoạn chia hết (5 điểm)

Cho dãy n số nguyên a₁, a₂, …, a_n (có thể âm) và số nguyên dương 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 chia hết cho K.

Dữ liệu vào: Từ file văn bản DOANCHIA.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 DOANCHIA.OUT một số nguyên là số đoạn tìm được.

Ví dụ:

DOANCHIA.INP	DOANCHIA.OUT	Giải thích
`6 5` `4 5 0 -2 -3 1`	`7`	Ví dụ các đoạn (5), (5, 0), (0), (−2, −3), (4, 5, 0, −2, −3, 1), …

Ràng buộc:

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

Bài 4. Ba lô dã ngoại (6 điểm)

Bạn Nam chuẩn bị đi dã ngoại với chiếc ba lô chịu được khối lượng tối đa W. Có n đồ vật, đồ vật thứ i có khối lượng w_i và độ hữu ích v_i. Mỗi đồ vật chỉ có một chiếc.

Yêu cầu: Chọn một số đồ vật cho vào ba lô sao cho tổng khối lượng không vượt quá W và tổng độ hữu ích lớn nhất.

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

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

Kết quả: Ghi ra file văn bản CAITUI.OUT một số nguyên là tổng độ hữu ích lớn nhất.

Ví dụ:

CAITUI.INP	CAITUI.OUT	Giải thích
`4 10` `5 10` `4 40` `6 30` `3 50`	`90`	Chọn đồ vật thứ 2 và thứ 4: khối lượng 7, độ hữu ích 90.

Ràng buộc:

Có 30% số test với n ≤ 15, W ≤ 2 × 10⁴.
Có 70% số test với n ≤ 100, W ≤ 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