HSG lớp 9 Đà Nẵng 2012-2013

SỞ GIÁO DỤC - ĐÀO TẠO THÀNH PHỐ ĐÀ NẴNG ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 Năm học 2012 - 2013
Môn: Tin học
Thời gian: 150 phút (không tính thời gian giao đề)
(Đề thi gồm có 3 bài trong 2 trang)

---

Tổng quan đề thi

	Bộ tam hợp	Số lộn xộn	Dãy số
Tên bài làm	BL1.*	BL2.*	BL3.*
Dữ liệu vào	TAMHOP.INP	SOLONXON.INP	DAYSO.INP
Dữ liệu ra	TAMHOP.OUT	SOLONXON.OUT	DAYSO.OUT

Bài 1. Bộ tam hợp

Cho dãy số nguyên a₁, a₂, …, aₙ, các số khác nhau từng đôi một (3 ≤ n ≤ 5000; với mọi i ta có |aᵢ| ≤ 10⁶). Bộ ba số aᵢ, aⱼ, aₖ (i, j, k đôi một khác nhau) được gọi là bộ tam hợp nếu có một số bất kỳ trong ba số đó bằng trung bình cộng của hai số còn lại.

Yêu cầu: Hãy đếm số lượng bộ tam hợp và tìm bộ tam hợp có tổng giá trị của ba số là lớn nhất.

Dữ liệu vào: Đọc từ file văn bản TAMHOP.INP có cấu trúc như sau:

• Dòng 1 chứa số n;
• Dòng 2 chứa n số a₁, a₂, …, aₙ cách nhau ít nhất một dấu cách.

Dữ liệu ra: Ghi ra file văn bản TAMHOP.OUT có cấu trúc như sau:

• Dòng 1 ghi một số nguyên dương là số lượng bộ tam hợp tìm được;
• Dòng 2 ghi tổng giá trị ba số của bộ tam hợp là lớn nhất.

Ví dụ:

TAMHOP.INP	TAMHOP.OUT
7 6 1 9 2 3 4 8	5 18

Giải thích ví dụ: Có 5 bộ tam hợp tìm được là: (1, 2, 3); (2, 3, 4); (2, 4, 6); (4, 6, 8); (3, 6, 9).

Bài 2. Số lộn xộn

Một số lộn xộn là một xâu chứa các chữ số và các dấu ? (như 36?1?8). Ta nói một số X thích hợp với số lộn xộn W nếu chúng có độ dài giống nhau, và X nhận được từ W bằng cách thay mỗi dấu ? bằng một chữ số (có thể thay thế một dấu ? với một chữ số bất kỳ). Ví dụ: 365198 thích hợp với số lộn xộn 36?1?8, nhưng 360199, 361028, 36128 là không thích hợp.

Yêu cầu: Cho số lộn xộn W và số X, cả 2 có độ dài n (1 ≤ n ≤ 10), đếm số các số có n chữ số thích hợp với W và lớn hơn X.

Dữ liệu vào: Đọc từ file văn bản SOLONXON.INP gồm nhiều test, mỗi test chứa hai dòng có độ dài giống nhau. Dòng đầu là số W và dòng hai là số nguyên X. Kết thúc file là dòng chứa dấu #.

Dữ liệu ra: Ghi ra file văn bản SOLONXON.OUT gồm nhiều dòng, mỗi test đưa ra một dòng là số lượng các số thích hợp với W và lớn hơn X.

Ví dụ:

SOLONXON.INP	SOLONXON.OUT
8?3 910 ? 5 #	0 4

Bài 3. Dãy số

Cho một dãy số nguyên a₁, a₂, …, aₙ. Với mọi i > 1, aᵢ thoả các yêu cầu sau:

1. aᵢ là số nguyên nhỏ nhất thỏa mãn hai điều kiện dưới đây;
2. aᵢ > aᵢ₋₁;
3. Tổng các chữ số của aᵢ bằng tổng các chữ số của aᵢ₋₁ sau khi đã nhân cho 4 (tức là tổng các chữ số của số 4 × aᵢ₋₁).

Yêu cầu: Cho a₁ và n, tìm aₙ.

Dữ liệu vào: Đọc từ file văn bản DAYSO.INP chỉ một dòng chứa hai số a₁ (0 < a₁ < 20) và n (0 < n < 10000).

Dữ liệu ra: Ghi ra file văn bản DAYSO.OUT chứa một số aₙ.

Ví dụ:

DAYSO.INP	DAYSO.OUT
4 5	79

Giải thích ví dụ: a1 = 4; a2 = 7; a3 = 19; a4 = 49; a5 = 79.

---

Chú ý: Cán bộ coi thi không giải thích gì thêm.