Đề thi chọn HSG môn Tin học khối lớp 8, 9

Đề 003. Đề tham khảo số 3

ĐỀ CHÍNH THỨC (Đề thi gồm có 02 trang)

TỔNG QUAN ĐỀ THI

Bài	Tên bài	Tên tệp chương trình	Tên tệp dữ liệu vào	Tên tệp kết quả
1	Tìm số thân thiện	SOTT.*	SOTT.INP	SOTT.OUT
2	Tìm số đối xứng với một số cho trước	SODX.*	SODX.INP	SODX.OUT
3	Chia kẹo cho đều	CHIAKEO.*	CHIAKEO.INP	CHIAKEO.OUT
4	Đóng gạo vào bao	DGVB.*	DGVB.INP	DGVB.INP

Thí sinh có thể sử dụng ngôn ngữ lập trình Pascal, C++, Python.

Bài 1. Tìm số thân thiện (5,0 điểm)

Số thân thiện là những số mà nó và số đảo ngược của nó là hai số nguyên tố cùng nhau (hai số có ước chung lớn nhất là 1). Ví dụ với số 23, số đảo ngược của nó là 32. Hai số này có ước chung lớn nhất là 1. Những số như thế được gọi là số thân thiện, tức là số 23 được gọi là số thân thiện, số 32 cũng được gọi là số thân thiện.

Yêu cầu: Với 2 số nguyên a, b (10≤a≤b≤30000). Hãy đếm xem trong khoảng từ a đến b (kể cả a và b) có bao nhiêu số thân thiện.

Dữ liệu: Tệp SOTT.INP gồm một hàng chứa 2 số a, b. Hai số được cách nhau bằng một khoảng trắng.

Kết quả: Tệp SOTT.OUT gồm một hàng là kết quả của bài toán.

Ví dụ:

SOTT.INP	SOTT.OUT
20 30	3

Bài 2. Tìm số đối xứng với một số cho trước (5,0 điểm)

Số đối xứng là số có thể viết từ phải sang trái các chữ số của nó ta vẫn được chính nó. Từ một số có hai chữ số, ta có thể nhận được một số đối xứng theo cách sau đây: lấy số ban đầu cộng với số phản xạ gương của nó, tức là số nhận được bằng cách đọc các chữ số từ phải sang trái; Nếu kết quả cộng lại chưa phải là số đối xứng, lấy kết quả đó lại cộng với ánh xạ gương của nó và tiếp tục như vậy cho tới khi nhận được số đối xứng.

Ví dụ: từ số ban đầu là 93 ta có 93 + 39 = 132; vì 132 chưa phải là số đối xứng nên ta thực hiện tiếp tục 132 + 231 = 363. Như vậy 363 là số đối xứng tương ứng với 93.

Yêu cầu: Viết chương trình tìm số đối xứng tương ứng với một số cho trước.

Dữ liệu: Tệp SODX.INP gồm một hàng là số tự nhiên N (11 < N < 10^6).

Kết quả: Tệp SODX.OUT chứa số đối xứng tìm được.

Ví dụ:

SODX.INP	SODX.OUT
93	363

Bài 3. Chia kẹo cho đều (5,0 điểm)

Cho n gói kẹo, gói thứ i có ai viên. Hãy chia các gói thành 2 phần sao cho tổng số kẹo

chênh lệch giữa 2 phần là ít nhất.

Dữ liệu vào: Tệp CHIAKEO.INP có 2 hàng. Hàng đầu là số tự nhiên n (1<n<=50). Hàng thứ 2 chứa dãy số tự nhiên a = a1, a2, ..., an. Với ai là trọng lượng của gói kẹo thứ i (1<ai<=100).

Kết quả ra: Tệp CHIAKEO.OUT có 2 hàng. Hàng 1 là phần kẹo gồm các gói kẹo có giá trị nhỏ hơn. Hàng 2 là phần kẹo gồm các gói kẹo có giá trị lớn hơn.

Ví dụ:

CHIAKEO.INP	CHIAKEO.OUT	Giải thích
5 4 8 24 32 5	4 5 8 24 32	Các gói kẹo nhỏ hơn: [4, 5, 8, 24] Các gói kẹo lớn hơn: [32]

Bài 4. Đóng gạo vào bao (5,0 điểm)

Một nhà máy xây xát cần đóng gói gạo vào các loại bao 100 kg, 50 kg, 20 kg, 10 kg, 5 kg. Với mỗi 1oại bao chỉ được đóng gói khi đủ số lượng quy định cho 1oại bao đó. Tuy nhiên công ty sản xuất các loại bao thì cung cấp số lượng bao theo từng đợt với số lượng từng loại khác nhau.

Yêu cầu: Với số lượng gạo và số lượng bao của từng loại cho trước, hãy tìm một phương án đóng gói sao cho số lượng gạo thừa không được đóng gói (nếu có) là ít nhất.

Dữ liệu vào: Tệp DGVB.INP bao gồm:

• Dòng đầu ghi số lựog gạo N cần phải đóng gói (0 < N < 1000000).

• Dòng thứ hai ghi 5 số tự nhiên cho biết số lượng bao của từng loại theo thứ tự 100kg, 50kg, 20kg, 10kg, 5kg.

Dữ liệu ra: Tệp DGVB.OUT bao gồm:

• Dòng đầu ghi số gạo thừa không được đóng gói.

• Dòng thứ hai ghi 5 so nguyên tương ứng là số lượng bao đã sử dụng.

Ví dụ:

DGVB.INP	DGVB.INP
1000 5 0 20 30 45	0 5 0 20 10 0
950 10 0 20 0 0	10 9 0 2 0 0

---Hết---