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

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

ĐỀ SỐ 08 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	Lỗ hổng của chữ số	LOHONG.*	LOHONG.INP	LOHONG.OUT	4
2	Bộ ba chữ số	BOBA.*	BOBA.INP	BOBA.OUT	4
3	Độ bền của số	DOBEN.*	DOBEN.INP	DOBEN.OUT	6
4	Xếp hàng vào lớp	XEPNGUOI.*	XEPNGUOI.INP	XEPNGUOI.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. Lỗ hổng của chữ số (4 điểm)

Khi viết tay, một số chữ số có “lỗ hổng” (vùng khép kín): các chữ số 0, 4, 6, 9 có 1 lỗ, chữ số 8 có 2 lỗ, các chữ số 1, 2, 3, 5, 7 không có lỗ nào.

Yêu cầu: Cho số nguyên dương n, hãy tính tổng số lỗ hổng của tất cả các chữ số của n và cho biết chữ số xuất hiện nhiều lần nhất trong n (nếu có nhiều chữ số như vậy thì chọn chữ số nhỏ nhất).

Dữ liệu vào: Từ file văn bản LOHONG.INP gồm một số nguyên dương n (không có chữ số 0 ở đầu).

Kết quả: Ghi ra file văn bản LOHONG.OUT gồm hai dòng: tổng số lỗ hổng và chữ số xuất hiện nhiều nhất.

Ví dụ:

LOHONG.INP	LOHONG.OUT	Giải thích
8096	5 0	8 có 2 lỗ, 0, 9, 6 mỗi chữ số 1 lỗ. Bốn chữ số đều xuất hiện một lần, chọn chữ số nhỏ nhất là 0.

Ràng buộc:

• Có 50% số test với n ≤ 10¹⁸.
• Có 50% số test với n có tới 10⁶ chữ số.

Bài 2. Bộ ba chữ số (4 điểm)

Cho số tự nhiên N.

Yêu cầu:

1. Xóa các chữ số lặp lại của N: mỗi chữ số chỉ giữ lại lần xuất hiện đầu tiên (tính từ trái sang).
2. Từ các chữ số của số vừa thu được, liệt kê tất cả các bộ ba chữ số khác nhau a, b, c thỏa mãn a = b + c và b > c. Mỗi bộ ba được viết thành số có ba chữ số abc, liệt kê theo thứ tự giảm dần.

Dữ liệu vào: Từ file văn bản BOBA.INP gồm một số tự nhiên N (không có chữ số 0 ở đầu).

Kết quả: Ghi ra file văn bản BOBA.OUT gồm hai dòng: dòng thứ nhất ghi số sau khi xóa các chữ số lặp lại; dòng thứ hai ghi các bộ ba theo thứ tự giảm dần, cách nhau một dấu cách, nếu không có bộ ba nào thì ghi -1.

Ví dụ:

BOBA.INP	BOBA.OUT	Giải thích
870694359938	87069435 963 954 853 743	Các chữ số 8, 7, 0, 6, 9, 4, 3, 5. Ví dụ 9 = 6 + 3 cho bộ ba 963.

Ràng buộc:

• Có 50% số test với N có không quá 18 chữ số.
• Có 50% số test với N có tới 10⁶ chữ số.

Bài 3. Độ bền của số (6 điểm)

Độ bền của một số tự nhiên x được định nghĩa như sau:

• Nếu x có một chữ số thì độ bền của x bằng 0.
• Nếu x có từ hai chữ số trở lên thì độ bền của x bằng độ bền của tích các chữ số của x, cộng thêm 1.

Ví dụ: 77 → 49 → 36 → 18 → 8, nên độ bền của 77 là 4.

Yêu cầu: Cho q số n₁, n₂, …, với mỗi số n_i hãy cho biết độ bền của n_i và số tự nhiên nhỏ hơn n_i có độ bền lớn nhất (nếu có nhiều số như vậy thì chọn số nhỏ nhất).

Dữ liệu vào: Từ file văn bản DOBEN.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 chứa một số nguyên dương n_i.

Kết quả: Ghi ra file văn bản DOBEN.OUT gồm q dòng, mỗi dòng hai số: độ bền của n_i và số tìm được.

Ví dụ:

DOBEN.INP	DOBEN.OUT	Giải thích
2 82 100	2 77 1 77	82 → 16 → 6 nên độ bền là 2; 100 → 0 nên độ bền là 1. Trong các số nhỏ hơn 82 (và nhỏ hơn 100), số 77 có độ bền lớn nhất là 4.

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 ≤ 5 × 10⁵.

Bài 4. Xếp hàng vào lớp (6 điểm)

Có n học sinh đeo số thứ tự từ 1 đến n, đứng thành một hàng dọc (hàng 1). Cô giáo chuyển các bạn sang hàng 2 theo quy tắc: bạn đứng đầu hàng 1 chuyển sang cuối hàng 2, bạn đứng đầu tiếp theo chuyển xuống cuối hàng 1, bạn tiếp theo sang cuối hàng 2, bạn tiếp theo xuống cuối hàng 1, … cứ xen kẽ như vậy cho đến khi hàng 1 hết người.

Yêu cầu: Tìm cách xếp các bạn ở hàng 1 ban đầu để sau khi chuyển xong, hàng 2 (tính từ đầu hàng) có số thứ tự lần lượt là 1, 2, …, n.

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

Kết quả: Ghi ra file văn bản XEPNGUOI.OUT gồm n số là số thứ tự của các bạn ở hàng 1 ban đầu, tính từ đầu hàng, cách nhau một dấu cách.

Ví dụ:

XEPNGUOI.INP	XEPNGUOI.OUT	Giải thích
3	1 3 2	Hàng 1: 1 3 2. Bạn 1 sang hàng 2; bạn 3 xuống cuối hàng 1 (còn 2 3); bạn 2 sang hàng 2; bạn 3 sang hàng 2.
5	1 5 2 4 3

Ràng buộc:

• Có 30% số test với n ≤ 8.
• Có 30% số test với n ≤ 2000.
• Có 40% 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.