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

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

ĐỀ SỐ 29 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	Diện tích và chu vi	CHUVI.*	CHUVI.INP	CHUVI.OUT	3
2	Đi thuyền tham quan	THAMQUAN.*	THAMQUAN.INP	THAMQUAN.OUT	5
3	Mảnh vườn sinh lời nhất	TONGBANG.*	TONGBANG.INP	TONGBANG.OUT	6
4	Xây tháp	XAYTHAP.*	XAYTHAP.INP	XAYTHAP.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. Diện tích và chu vi (3 điểm)

Trên giấy kẻ ô vuông m × n, bạn Hoa tô màu một số ô (ô ghi 1 là ô được tô, ô ghi 0 là ô trắng). Mỗi ô là hình vuông cạnh 1.

Yêu cầu: Tính tổng diện tích phần được tô và tổng chu vi của phần được tô. Chu vi là tổng độ dài các cạnh ô vuông nằm giữa một ô được tô và một ô trắng, hoặc giữa một ô được tô và mép giấy.

Dữ liệu vào: Từ file văn bản CHUVI.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 là một xâu n kí tự 0 hoặc 1.

Kết quả: Ghi ra file văn bản CHUVI.OUT hai số: diện tích và chu vi.

Ví dụ:

CHUVI.INP	CHUVI.OUT
3 4 0110 1110 0100	6 12

Ràng buộc: m, n ≤ 500.

Bài 2. Đi thuyền tham quan (5 điểm)

Một đoàn n học sinh đi tham quan đầm sen bằng thuyền. Mỗi thuyền chở tối đa 2 người và tổng cân nặng không vượt quá C kg. Bạn thứ i nặng w_i kg (w_i ≤ C).

Yêu cầu: Tìm số thuyền ít nhất cần dùng.

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

• Dòng đầu tiên chứa hai số nguyên dương n và C.
• Dòng thứ hai chứa n số nguyên dương w₁, w₂, …, w_n.

Kết quả: Ghi ra file văn bản THAMQUAN.OUT một số nguyên là số thuyền ít nhất.

Ví dụ:

THAMQUAN.INP	THAMQUAN.OUT	Giải thích
6 100 70 50 80 20 50 30	3	Các thuyền: (80, 20), (70, 30), (50, 50).

Ràng buộc:

• Có 30% số test với n ≤ 10.
• Có 70% số test với n ≤ 2 × 10⁵.

Bài 3. Mảnh vườn sinh lời nhất (6 điểm)

Một khu vườn được chia thành lưới m × n ô; ô ở hàng i, cột j cho lợi nhuận a_ij (có thể âm nếu ô đó thua lỗ). Chủ vườn muốn giữ lại đúng một mảnh hình chữ nhật (gồm các ô liên tiếp theo hàng và theo cột, ít nhất một ô) có tổng lợi nhuận lớn nhất.

Yêu cầu: Tìm tổng lợi nhuận lớn nhất của một hình chữ nhật con.

Dữ liệu vào: Từ file văn bản TONGBANG.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 TONGBANG.OUT một số nguyên là tổng lớn nhất.

Ví dụ:

TONGBANG.INP	TONGBANG.OUT	Giải thích
4 5 1 2 -1 -4 -20 -8 -3 4 2 1 3 8 10 1 3 -4 -1 1 7 -6	29	Hình chữ nhật từ hàng 2 đến hàng 4, cột 2 đến cột 4.

Ràng buộc:

• Có 40% số test với m, n ≤ 30.
• Có 60% số test với m, n ≤ 100.

Bài 4. Xây tháp (6 điểm)

Trên băng chuyền lần lượt chạy qua n khối gỗ, khối thứ i có kích thước s_i và chiều cao h_i. Khi một khối chạy qua, bạn có thể lấy nó đặt lên đỉnh tháp đang xây, hoặc bỏ qua (không lấy lại được). Một khối chỉ đặt được lên khối có kích thước lớn hơn hẳn nó.

Yêu cầu: Tìm chiều cao lớn nhất của tháp có thể xây.

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

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

Kết quả: Ghi ra file văn bản XAYTHAP.OUT một số nguyên là chiều cao lớn nhất.

Ví dụ:

XAYTHAP.INP	XAYTHAP.OUT	Giải thích
6 5 3 8 2 6 4 3 5 7 1 2 2	13	Lấy các khối kích thước 8, 6, 3, 2: chiều cao 2 + 4 + 5 + 2 = 13.

Ràng buộc:

• Có 40% số test với n ≤ 1000.
• Có 60% số test với n ≤ 5 × 10⁴.

Lời giải và bộ test của đề này (có phí)

Hướng dẫn giải chi tiết, code Python và C++ đã được kiểm chứng, cùng bộ test và công cụ chấm cham.py, có trong bộ tài liệu đầy đủ (có phí).

Thầy cô và các em muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.

Muốn xem trước cách trình bày lời giải, hãy xem Đề số 01 (có lời giải miễn phí).

Do số lượng đề bài, bài giải và bộ test rất nhiều nên tác giả đang kiểm tra từng bước. Thầy cô và các em học sinh nếu thấy sai sót xin vui lòng liên hệ tác giả qua Facebook hoặc Zalo (0972465159). Xin chân thành cảm ơn.