HSG lớp 9 Bà Rịa - Vũng Tàu 2015-2016

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH BÀ RỊA - VŨNG TÀU ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 Năm học 2015 - 2016
Môn thi: Tin học - Ngày thi: 25/03/2016
Thời gian làm bài thi: 150 phút
(Đề thi có 2 trang)

---

Bài 1. Đếm số phong phú (7 điểm)

Tên file chương trình: ABUNDENT.???

Số phong phú là số có tổng các ước số nguyên của nó kể cả số 1 (không kể chính nó) lớn hơn nó. Ví dụ: số 6 có tổng các ước 1 + 2 + 3 = 6, không là số phong phú. Số 12 có tổng các ước là 1 + 2 + 3 + 4 + 6 = 16 (lớn hơn 12) là số phong phú.

Yêu cầu: Hãy cho biết có bao nhiêu số phong phú không lớn hơn N.

Dữ liệu vào từ file ABUNDENT.INP: chứa duy nhất số nguyên N (0 < N ≤ 10⁵).

Kết quả ghi vào file ABUNDENT.OUT: ghi một số nguyên duy nhất là kết quả tìm được theo yêu cầu.

Ví dụ:

ABUNDENT.INP	ABUNDENT.OUT
24	4

Trong ví dụ trên có 4 số phong phú là 12, 18, 20, 24.

Bài 2. Ghép số (7 điểm)

Tên file chương trình: NUMBER.PAS

Cho 3 số gồm 0, 1, 2. Người ta muốn tạo ra những số có N chữ số từ 3 số trên sao cho số vừa tạo thỏa mãn các yêu cầu sau:

• Là số chia hết cho 5.
• Không có 2 chữ số liền kề giống nhau.
• Chữ số đầu tiên lớn hơn 0.

Ví dụ: với n = 4, các số thỏa mãn: 2120, 1210, … Số không thỏa mãn: 2110 (2 chữ số liền kề giống nhau), 2021 (không chia hết cho 5), …

Yêu cầu: Hãy cho biết có bao nhiêu số thỏa mãn các yêu cầu trên.

Dữ liệu vào: Từ file NUMBER.INP chứa duy nhất số nguyên N (0 < N ≤ 21).

Dữ liệu ra: Ghi vào file NUMBER.OUT kết quả tìm được theo yêu cầu.

Ví dụ:

NUMBER.INP	NUMBER.OUT
4	6

Bài 3. Nối xích (6 điểm)

Tên file chương trình: CONCHAIN.PAS

Cho một dãy N mắt xích lần lượt có độ bền là a₁, a₂, …, a_N. Nếu nối hai mắt xích nằm cạnh nhau là mắt xích thứ i và i + 1 (1 ≤ i < N) thì độ bền của mối nối là dᵢ tính theo công thức:

• dᵢ = 0 khi aᵢ ≥ aᵢ₊₁;
• dᵢ = aᵢ₊₁ - aᵢ khi aᵢ < aᵢ₊₁.

Khi nối tất cả các mắt xích nằm cạnh nhau thành một dây xích thì độ bền của dây xích bằng tổng độ bền của từng mắt xích cộng với tổng độ bền của từng mối nối.

Yêu cầu: Hãy tìm cách sắp xếp các mắt xích sao cho độ bền của dây xích tạo thành là lớn nhất có thể.

Dữ liệu vào: Từ file CONCHAIN.INP:

• Dòng đầu tiên là số nguyên dương N (N ≤ 10⁵).
• N dòng tiếp theo, mỗi dòng là một số nguyên dương aᵢ (aᵢ ≤ 10⁶).

Dữ liệu ra: Ghi vào file CONCHAIN.OUT một số nguyên là tổng độ bền lớn nhất của dây xích tạo thành.

Ví dụ:

CONCHAIN.INP	CONCHAIN.OUT
5 5 7 1 4 3	28