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

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

ĐỀ SỐ 28 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	Số đảo ngược	SONGUOC.*	SONGUOC.INP	SONGUOC.OUT	4
2	Độ mạnh của mật khẩu	MATKHAU.*	MATKHAU.INP	MATKHAU.OUT	4
3	Vùng phủ sóng	PHUSONG.*	PHUSONG.INP	PHUSONG.OUT	6
4	Chọn quà quanh bàn tròn	CHONQUA.*	CHONQUA.INP	CHONQUA.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. Số đảo ngược (4 điểm)

Số đảo ngược của n là số nhận được khi viết các chữ số của n theo thứ tự ngược lại (bỏ các chữ số 0 ở đầu nếu có). Ví dụ số đảo ngược của 1230 là 321.

Yêu cầu: Cho số nguyên dương n, hãy tìm số đảo ngược r của n, cho biết n có phải số đối xứng (n = r) không, và tính n + r.

Dữ liệu vào: Từ file văn bản SONGUOC.INP gồm một số nguyên dương n.

Kết quả: Ghi ra file văn bản SONGUOC.OUT gồm ba dòng: r; YES nếu n là số đối xứng, ngược lại NO; n + r.

Ví dụ:

SONGUOC.INP	SONGUOC.OUT
1230	321 NO 1551
12321	12321 YES 24642

Ràng buộc: n ≤ 10¹⁸.

Bài 2. Độ mạnh của mật khẩu (4 điểm)

Một hệ thống chấm điểm mật khẩu theo 6 tiêu chí, mỗi tiêu chí thỏa mãn được 1 điểm:

1. Có ít nhất 8 kí tự.
2. Có ít nhất một chữ cái in thường.
3. Có ít nhất một chữ cái in hoa.
4. Có ít nhất một chữ số.
5. Có ít nhất một kí tự đặc biệt trong các kí tự ! @ # $ % ^ & *.
6. Không có 3 kí tự giống nhau đứng liền nhau.

Yêu cầu: Chấm điểm q mật khẩu và đếm số mật khẩu đạt đủ 6 điểm.

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

• Dòng đầu tiên chứa số nguyên dương q.
• q dòng tiếp theo, mỗi dòng là một mật khẩu (từ 1 đến 100 kí tự, không có dấu cách).

Kết quả: Ghi ra file văn bản MATKHAU.OUT gồm hai dòng: dòng thứ nhất ghi điểm của q mật khẩu; dòng thứ hai ghi số mật khẩu đạt 6 điểm.

Ví dụ:

MATKHAU.INP	MATKHAU.OUT	Giải thích
4 abc123 Hsg@2025Tin aaaBBB111!!! P@ss	3 6 5 4 1	Mật khẩu thứ ba có 3 chữ a liền nhau nên không đạt tiêu chí 6.

Ràng buộc: q ≤ 10⁴.

Bài 3. Vùng phủ sóng (6 điểm)

Dọc một tuyến đường có n trạm phát sóng. Trạm thứ i phủ sóng các điểm có tọa độ nguyên từ l_i đến r_i (tính cả hai đầu).

Yêu cầu: Tìm số trạm lớn nhất cùng phủ sóng một điểm, và tọa độ nhỏ nhất của điểm đạt số trạm đó.

Dữ liệu vào: Từ file văn bản PHUSONG.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 hai số nguyên l_i, r_i (0 ≤ l_i ≤ r_i).

Kết quả: Ghi ra file văn bản PHUSONG.OUT hai số: số trạm lớn nhất và tọa độ điểm tìm được.

Ví dụ:

PHUSONG.INP	PHUSONG.OUT	Giải thích
4 1 5 3 8 6 9 4 7	3 4	Điểm 4 được trạm thứ nhất, thứ hai và thứ tư phủ sóng.

Ràng buộc:

• Có 40% số test với n ≤ 1000, tọa độ không quá 1000.
• Có 60% số test với n ≤ 2 × 10⁵, tọa độ không quá 10⁹.

Bài 4. Chọn quà quanh bàn tròn (6 điểm)

Có n hộp quà đặt quanh một bàn tròn, hộp thứ i có giá trị a_i; hộp thứ n đứng cạnh hộp thứ 1. Bạn được chọn một số hộp quà, nhưng không được chọn hai hộp đứng cạnh nhau.

Yêu cầu: Tìm tổng giá trị lớn nhất có thể chọn được.

Dữ liệu vào: Từ file văn bản CHONQUA.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 (0 ≤ a_i ≤ 10⁹).

Kết quả: Ghi ra file văn bản CHONQUA.OUT một số nguyên là tổng giá trị lớn nhất.

Ví dụ:

CHONQUA.INP	CHONQUA.OUT	Giải thích
5 5 3 1 7 6	12	Chọn hộp 1 và hộp 4. Không chọn được cả hộp 1 và hộp 5 vì chúng đứng cạnh nhau.

Ràng buộc:

• Có 30% số test với n ≤ 18.
• Có 70% số test với n ≤ 2 × 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.