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

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

ĐỀ SỐ 18 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	Ngày mai	NGAYMAI.*	NGAYMAI.INP	NGAYMAI.OUT	4
2	Đường chéo	DUONGCHEO.*	DUONGCHEO.INP	DUONGCHEO.OUT	5
3	Làm bánh	LAMBANH.*	LAMBANH.INP	LAMBANH.OUT	5
4	Số nguyên tố trong đoạn lớn	DEMNT.*	DEMNT.INP	DEMNT.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. Ngày mai (4 điểm)

Theo lịch Gregory: tháng 1, 3, 5, 7, 8, 10, 12 có 31 ngày; tháng 4, 6, 9, 11 có 30 ngày; tháng 2 có 29 ngày nếu là năm nhuận và 28 ngày nếu không. 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.

Yêu cầu: Cho một ngày hợp lệ d/m/y, hãy cho biết ngày hôm sau và ngày d/m/y là ngày thứ mấy trong năm.

Dữ liệu vào: Từ file văn bản NGAYMAI.INP gồm một dòng chứa ba số nguyên d, m, y.

Kết quả: Ghi ra file văn bản NGAYMAI.OUT gồm hai dòng: dòng thứ nhất ghi ngày, tháng, năm của ngày hôm sau; dòng thứ hai ghi số thứ tự của ngày d/m/y trong năm.

Ví dụ:

NGAYMAI.INP	NGAYMAI.OUT	Giải thích
28 2 2024	29 2 2024 59	2024 là năm nhuận nên có ngày 29/2.
31 12 2023	1 1 2024 365

Ràng buộc:

• Có 50% số test với y ≤ 9999.
• Có 50% số test với y ≤ 10⁹.

Bài 2. Đường chéo (5 điểm)

Cho bảng vuông n × n các số nguyên. Đường chéo chính đi từ góc trên trái xuống góc dưới phải; đường chéo phụ đi từ góc trên phải xuống góc dưới trái. Ngoài đường chéo chính, còn có các đường chéo song song với nó (tổng cộng 2n − 1 đường chéo, kể cả hai đường chéo chỉ gồm một ô ở hai góc).

Yêu cầu: Tính tổng các số trên đường chéo chính, tổng các số trên đường chéo phụ, và tổng lớn nhất trong 2n − 1 đường chéo song song với đường chéo chính.

Dữ liệu vào: Từ file văn bản DUONGCHEO.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 n số nguyên có giá trị tuyệt đối không quá 10⁹.

Kết quả: Ghi ra file văn bản DUONGCHEO.OUT ba số theo thứ tự trên.

Ví dụ:

DUONGCHEO.INP	DUONGCHEO.OUT	Giải thích
3 1 2 3 4 5 6 7 8 9	15 15 15	Các đường chéo song song: 7, 4 + 8, 1 + 5 + 9, 2 + 6, 3.
3 1 -2 9 8 -5 1 7 6 2	-2 11 14	Đường chéo 8 + 6 có tổng lớn nhất là 14.

Ràng buộc:

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

Bài 3. Làm bánh (5 điểm)

Tiệm bánh có n thợ làm việc cùng lúc. Thợ thứ i làm xong một chiếc bánh sau đúng t_i phút, làm xong chiếc này thì làm ngay chiếc tiếp theo.

Yêu cầu: Tính thời gian ít nhất (tính bằng phút, kể từ lúc bắt đầu) để cả tiệm làm xong ít nhất M chiếc bánh.

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

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

Kết quả: Ghi ra file văn bản LAMBANH.OUT một số nguyên là thời gian ít nhất.

Ví dụ:

LAMBANH.INP	LAMBANH.OUT	Giải thích
3 10 3 5 10	18	Sau 18 phút ba thợ làm được 6 + 3 + 1 = 10 bánh; sau 17 phút chỉ được 5 + 3 + 1 = 9 bánh.

Ràng buộc:

• Có 40% số test với n ≤ 100, M ≤ 10⁴, t_i ≤ 10⁴.
• Có 60% số test với n ≤ 5 × 10⁴, M ≤ 10⁹, t_i ≤ 10⁹.

Bài 4. Số nguyên tố trong đoạn lớn (6 điểm)

Yêu cầu: Cho đoạn [L, R], hãy đếm số lượng số nguyên tố trong đoạn và tìm số nguyên tố lớn nhất trong đoạn.

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

Kết quả: Ghi ra file văn bản DEMNT.OUT hai số: số lượng số nguyên tố trong đoạn và số nguyên tố lớn nhất trong đoạn (ghi -1 nếu đoạn không có số nguyên tố nào).

Ví dụ:

DEMNT.INP	DEMNT.OUT	Giải thích
10 30	6 29	11, 13, 17, 19, 23, 29.
90 96	0 -1

Ràng buộc:

• Có 40% số test với R ≤ 10⁵.
• Có 60% số test với R ≤ 10¹² và R − L ≤ 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.