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

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

ĐỀ SỐ 20 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	Đếm năm nhuận	NAMNHUAN.*	NAMNHUAN.INP	NAMNHUAN.OUT	3
2	Bảng xếp hạng	XEPHANG.*	XEPHANG.INP	XEPHANG.OUT	5
3	Đoạn tăng dài nhất	DAYTANG.*	DAYTANG.INP	DAYTANG.OUT	6
4	Dãy con tăng dài nhất	LIS.*	LIS.INP	LIS.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. Đếm năm nhuận (3 điểm)

Năm nhuận là năm chia hết cho 400, hoặc chia hết cho 4 nhưng không chia hết cho 100. Ví dụ 2000 và 2024 là năm nhuận, 1900 và 2023 thì không.

Yêu cầu: Đếm số năm nhuận từ năm a đến năm b (tính cả a và b).

Dữ liệu vào: Từ file văn bản NAMNHUAN.INP gồm một dòng chứa hai số nguyên dương a ≤ b.

Kết quả: Ghi ra file văn bản NAMNHUAN.OUT một số nguyên là số năm nhuận.

Ví dụ:

NAMNHUAN.INP	NAMNHUAN.OUT	Giải thích
1896 1904	2	1896 và 1904; năm 1900 không nhuận.
1 2024	491

Ràng buộc:

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

Bài 2. Bảng xếp hạng (5 điểm)

Kết thúc kì thi, ban tổ chức có danh sách n thí sinh gồm tên (viết liền, chỉ gồm chữ cái tiếng Anh, các tên đôi một khác nhau) và điểm (số nguyên).

Yêu cầu: Lập bảng xếp hạng: sắp xếp theo điểm giảm dần; cùng điểm thì theo tên tăng dần (so sánh theo mã ASCII, tức chữ in hoa đứng trước chữ in thường). Thí sinh cùng điểm có cùng hạng; hạng của một thí sinh bằng 1 cộng số thí sinh có điểm cao hơn hẳn.

Dữ liệu vào: Từ file văn bản XEPHANG.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 tên và điểm của một thí sinh (0 ≤ điểm ≤ 10⁵).

Kết quả: Ghi ra file văn bản XEPHANG.OUT gồm n dòng theo thứ tự của bảng xếp hạng, mỗi dòng ghi hạng, tên và điểm.

Ví dụ:

XEPHANG.INP	XEPHANG.OUT
5 Minh 85 An 92 Lan 85 Binh 70 Hoa 92	1 An 92 1 Hoa 92 3 Lan 85 3 Minh 85 5 Binh 70

Ràng buộc:

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

Bài 3. Đoạn tăng dài nhất (6 điểm)

Cho dãy n số nguyên a₁, a₂, …, a_n. Được phép xóa tối đa một phần tử khỏi dãy (hoặc không xóa phần tử nào).

Yêu cầu: Tìm độ dài lớn nhất của một đoạn các phần tử liên tiếp tăng ngặt trong dãy thu được.

Dữ liệu vào: Từ file văn bản DAYTANG.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 a₁, a₂, …, a_n (|a_i| ≤ 10⁹).

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

Ví dụ:

DAYTANG.INP	DAYTANG.OUT	Giải thích
7 1 3 5 4 7 8 2	5	Xóa số 4 được đoạn 1, 3, 5, 7, 8.

Ràng buộc:

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

Bài 4. Dãy con tăng dài nhất (6 điểm)

Cho dãy n số nguyên a₁, a₂, …, a_n. Một dãy con được tạo bằng cách xóa đi một số phần tử (có thể không xóa phần tử nào) và giữ nguyên thứ tự các phần tử còn lại; các phần tử của dãy con không cần đứng liền nhau trong dãy ban đầu.

Yêu cầu: Tìm độ dài của dãy con tăng ngặt dài nhất.

Dữ liệu vào: Từ file văn bản LIS.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 a₁, a₂, …, a_n (|a_i| ≤ 10⁹).

Kết quả: Ghi ra file văn bản LIS.OUT một số nguyên là độ dài dãy con tăng dài nhất.

Ví dụ:

LIS.INP	LIS.OUT	Giải thích
8 10 9 2 5 3 7 101 18	4	Ví dụ dãy con 2, 3, 7, 18.

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 ≤ 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.