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

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

ĐỀ SỐ 15 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	Gửi tiết kiệm	TIETKIEM.*	TIETKIEM.INP	TIETKIEM.OUT	3
2	Chia cùng số dư	CUNGDU.*	CUNGDU.INP	CUNGDU.OUT	5
3	Phân tích ra thừa số nguyên tố	PHANTICH.*	PHANTICH.INP	PHANTICH.OUT	6
4	Hai nhà gần nhau nhất	KHOANGCACH.*	KHOANGCACH.INP	KHOANGCACH.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. Gửi tiết kiệm (3 điểm)

Bạn Tý gửi T đồng vào ngân hàng với lãi suất L% mỗi tháng. Cuối mỗi tháng, ngân hàng tính tiền lãi bằng L% số tiền hiện có, làm tròn xuống đến đồng, rồi cộng tiền lãi vào số tiền gửi (lãi nhập gốc).

Yêu cầu: Cho biết sau ít nhất bao nhiêu tháng thì số tiền của Tý đạt ít nhất G đồng, và khi đó Tý có bao nhiêu tiền.

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

Kết quả: Ghi ra file văn bản TIETKIEM.OUT hai số: số tháng và số tiền khi đó. Nếu không bao giờ đạt được G đồng thì ghi -1.

Ví dụ:

TIETKIEM.INP	TIETKIEM.OUT	Giải thích
1000000 1 1030000	3 1030301	1 000 000 → 1 010 000 → 1 020 100 → 1 030 301.
50 1 100	-1	Tiền lãi mỗi tháng là 1% của 50 đồng = 0,5 đồng, làm tròn xuống thành 0.

Ràng buộc: T ≤ 10⁹, 1 ≤ L ≤ 100, G ≤ 10¹⁸.

Bài 2. Chia cùng số dư (5 điểm)

Cho dãy n số nguyên dương a₁, a₂, …, a_n.

Yêu cầu: Tìm số nguyên dương x lớn nhất sao cho tất cả các số trong dãy khi chia cho x đều có cùng một số dư, và cho biết số dư đó.

Dữ liệu vào: Từ file văn bản CUNGDU.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 dương a₁, a₂, …, a_n.

Kết quả: Ghi ra file văn bản CUNGDU.OUT hai số x và số dư chung. Nếu x có thể lớn tùy ý (mọi số trong dãy bằng nhau) thì ghi -1.

Ví dụ:

CUNGDU.INP	CUNGDU.OUT	Giải thích
4 17 5 29 11	6 5	17, 5, 29, 11 chia 6 đều dư 5.

Ràng buộc:

• Có 50% số test với n ≤ 100, a_i ≤ 1000.
• Có 50% số test với n ≤ 10⁵, a_i ≤ 10¹⁸.

Bài 3. Phân tích ra thừa số nguyên tố (6 điểm)

Yêu cầu: Cho q số nguyên, hãy phân tích mỗi số ra thừa số nguyên tố.

Dữ liệu vào: Từ file văn bản PHANTICH.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 x (2 ≤ x ≤ 10⁶).

Kết quả: Ghi ra file văn bản PHANTICH.OUT gồm q dòng. Dòng thứ i ghi các thừa số nguyên tố của số thứ i theo thứ tự không giảm, ngăn cách bởi dấu chấm (thừa số nào lặp lại thì ghi lặp lại).

Ví dụ:

PHANTICH.INP	PHANTICH.OUT
3 84 100 13	2.2.3.7 2.2.5.5 13

Ràng buộc:

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

Bài 4. Hai nhà gần nhau nhất (6 điểm)

Dọc một con đường thẳng có n ngôi nhà, ngôi nhà thứ i ở vị trí a_i (có thể có nhiều nhà chung một vị trí, ví dụ các căn hộ trong cùng một tòa nhà).

Yêu cầu: Tìm khoảng cách nhỏ nhất giữa hai ngôi nhà khác nhau, và đếm số cặp nhà có khoảng cách đúng bằng giá trị nhỏ nhất đó.

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

• Dòng đầu tiên chứa số nguyên n (n ≥ 2).
• 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 KHOANGCACH.OUT hai số: khoảng cách nhỏ nhất và số cặp nhà.

Ví dụ:

KHOANGCACH.INP	KHOANGCACH.OUT	Giải thích
5 7 4 -3 -1 5	1 1	Chỉ có cặp 4 và 5.
6 2 9 2 9 2 5	0 4	Ba nhà ở vị trí 2 tạo 3 cặp, hai nhà ở vị trí 9 tạo 1 cặp.

Ràng buộc:

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