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

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

ĐỀ SỐ 02 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	Nén xâu	NENXAU.*	NENXAU.INP	NENXAU.OUT	4
2	Số nguyên tố láng giềng	NTGAN.*	NTGAN.INP	NTGAN.OUT	5
3	Xếp phòng	XEPPHONG.*	XEPPHONG.INP	XEPPHONG.OUT	5
4	Số bậc thang	BACTHANG.*	BACTHANG.INP	BACTHANG.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. Nén xâu (4 điểm)

Khi gõ tin nhắn trên chiếc điện thoại cũ, bàn phím bị kẹt nên mỗi lần bấm một chữ cái thì chữ đó có thể bị lặp lại nhiều lần, đồng thời thỉnh thoảng lại chèn vào một chữ số. Ví dụ tên tranthithanhtam bị gõ thành 5trrraann3thhhhiii45ttthannh2taa64mmm.

Để khôi phục tin nhắn, ta làm như sau:

1. Xóa tất cả các chữ số trong xâu (đồng thời tính tổng các chữ số bị xóa).
2. Trong xâu còn lại, mỗi nhóm các chữ cái giống nhau đứng liền nhau chỉ giữ lại một chữ.

Yêu cầu: Cho xâu S đã bị gõ sai, hãy tính tổng các chữ số bị xóa và xâu sau khi khôi phục.

Dữ liệu vào: Từ file văn bản NENXAU.INP gồm một dòng chứa xâu S chỉ gồm chữ cái in thường và chữ số, có ít nhất một chữ cái.

Kết quả: Ghi ra file văn bản NENXAU.OUT gồm hai dòng: dòng thứ nhất ghi tổng các chữ số bị xóa, dòng thứ hai ghi xâu sau khi khôi phục.

Ví dụ:

NENXAU.INP	NENXAU.OUT
5trrraann3thhhhiii45ttthannh2taa64mmm	29 tranthithanhtam

Giải thích: tổng các chữ số là 5 + 3 + 4 + 5 + 2 + 6 + 4 = 29. Lưu ý các chữ cái giống nhau chỉ bị gộp sau khi đã xóa chữ số, ví dụ aa3a thành a.

Ràng buộc: Gọi L là độ dài xâu S.

• Có 50% số test với L ≤ 1000.
• Có 50% số test với L ≤ 10⁶.

Bài 2. Số nguyên tố láng giềng (5 điểm)

Số nguyên tố là số tự nhiên lớn hơn 1 chỉ có hai ước là 1 và chính nó. Với mỗi số tự nhiên n ≥ 2, số nguyên tố láng giềng của n là số nguyên tố p khác n sao cho khoảng cách |p − n| nhỏ nhất. Nếu có hai số nguyên tố cách n như nhau thì chọn số nhỏ hơn.

Ví dụ: số nguyên tố láng giềng của 24 là 23, của 2 là 3, của 9 là 7 (7 và 11 cùng cách 9 hai đơn vị, chọn số nhỏ hơn).

Yêu cầu: Cho q số nguyên n₁, n₂, …, hãy tìm số nguyên tố láng giềng của từng số.

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

• Dòng đầu tiên chứa số nguyên dương q.
• q dòng tiếp theo, dòng thứ i chứa số nguyên n_i (n_i ≥ 2).

Kết quả: Ghi ra file văn bản NTGAN.OUT gồm q dòng, dòng thứ i ghi số nguyên tố láng giềng của n_i.

Ví dụ:

NTGAN.INP	NTGAN.OUT
4 24 2 9 12	23 3 7 11

Ràng buộc:

• Có 40% số test với q ≤ 100, n_i ≤ 10⁴.
• Có 60% số test với q ≤ 10⁵, n_i ≤ 10⁶.

Bài 3. Xếp phòng (5 điểm)

Một đoàn học sinh đi dã ngoại được chia thành n nhóm nhỏ, nhóm thứ i có a_i bạn (1 ≤ a_i ≤ 4). Khu nghỉ có nhiều phòng, mỗi phòng ở được tối đa 4 người. Các bạn cùng một nhóm phải ở chung một phòng, nhưng một phòng có thể xếp nhiều nhóm miễn là tổng số người không quá 4.

Yêu cầu: Tính số phòng ít nhất cần thuê.

Dữ liệu vào: Từ file văn bản XEPPHONG.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.

Kết quả: Ghi ra file văn bản XEPPHONG.OUT một số nguyên là số phòng ít nhất.

Ví dụ:

XEPPHONG.INP	XEPPHONG.OUT	Giải thích
6 1 4 2 3 2 3	4	Các phòng: (4), (3, 1), (3), (2, 2).

Ràng buộc:

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

Bài 4. Số bậc thang (6 điểm)

Số bậc thang là số nguyên dương mà mỗi chữ số (kể từ chữ số thứ hai) đều không nhỏ hơn chữ số đứng ngay trước nó, giống như các bậc thang đi lên hoặc đi ngang. Ví dụ: 7, 123, 233, 1179 là các số bậc thang; 10, 132, 998 không phải.

Yêu cầu: Cho hai số nguyên dương a ≤ b, hãy đếm số lượng số bậc thang trong đoạn [a, b].

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

Kết quả: Ghi ra file văn bản BACTHANG.OUT một số nguyên là số lượng số bậc thang tìm được.

Ví dụ:

BACTHANG.INP	BACTHANG.OUT	Giải thích
32 40	7	Các số 33, 34, 35, 36, 37, 38, 39.
1 100	54	9 số có một chữ số và 45 số có hai chữ số.

Ràng buộc:

• Có 40% số test với b ≤ 10⁶.
• Có 30% số test với b ≤ 10⁹.
• Có 30% số test với b ≤ 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.