HSG lớp 9 Hà Nội 2012-2013

SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI ĐỀ CHÍNH THỨC

KỲ THI HỌC SINH GIỎI THÀNH PHỐ - LỚP 9 Năm học 2012 - 2013
Môn thi: Tin học - Ngày thi: 05/04/2013
Thời gian làm bài: 150 phút
(Đề thi gồm 02 trang)

---

Câu 1. Tìm số (8 điểm)

Tên tệp chương trình: CAU1.PAS

Cho trước số nguyên dương k (k ≤ 10⁵).

Yêu cầu:

• Tìm ước nguyên tố nhỏ nhất của k;
• Tìm tất cả các bộ ba số nguyên tố x, y, z (x ≤ y ≤ z) sao cho x + y + z = k.

Dữ liệu: Vào từ tệp văn bản BAI1.INP chứa số k.

Kết quả: Ghi ra tệp văn bản BAI1.OUT:

• Dòng thứ nhất ghi ước nguyên tố nhỏ nhất của k. Nếu không tìm được ghi số 0;
• Dòng thứ hai ghi n là số lượng bộ ba số nguyên tố tìm được. N dòng tiếp theo mỗi dòng ghi một bộ ba số nguyên tố thỏa mãn. Các bộ ba số được ghi theo thứ tự tăng dần của x. Nếu không tìm được bộ ba số thỏa mãn ghi số 0.

Ví dụ:

BAI1.INP	BAI1.OUT	Giải thích
10	2 1 2 3 5	- Ước nguyên tố nhỏ nhất của 10 là 2. - Số lượng các bộ số nguyên tố tìm được n = 1 tương ứng là 2, 3, 5.

Câu 2. Mua máy (6 điểm)

Tên tệp chương trình: CAU2.PAS

Một nhà máy cần gia công n sản phẩm nên phải mua một số máy để sản xuất. Mỗi sản phẩm thứ i (1 ≤ i ≤ n) được đưa tới nhà máy vào thời điểm dᵢ và gia công hết tᵢ đơn vị thời gian. Tại mỗi thời điểm, mỗi máy chỉ gia công một sản phẩm cho đến khi hoàn thành mới chuyển sang gia công sản phẩm khác. Mỗi sản phẩm khi đến nhà máy phải được gia công ngay lập tức.

Yêu cầu: Xác định xem nhà máy cần mua số lượng máy ít nhất là bao nhiêu để đảm bảo sản xuất.

Dữ liệu: Vào từ tệp văn bản BAI2.INP:

• Dòng đầu chứa số nguyên dương n không vượt quá 10⁴;
• n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương dᵢ và tᵢ, mỗi số không vượt quá 10⁵.

Kết quả: Ghi ra tệp văn bản BAI2.OUT số lượng máy cần mua.

Ví dụ:

BAI2.INP	BAI2.OUT	Giải thích
5 13 6 15 1 11 7 12 2 10 3	3	- Máy thứ nhất sẽ gia công lần lượt các sản phẩm thứ năm và thứ nhất. - Máy thứ hai sẽ gia công sản phẩm thứ ba. - Máy thứ ba sẽ gia công lần lượt các sản phẩm thứ tư và thứ hai.

Câu 3. Chữ số (6 điểm)

Tên tệp chương trình: CAU3.PAS

Xét dãy các số tự nhiên a₀, a₁, …, aₙ được xây dựng theo quy tắc sau:

• a₀ là một số tự nhiên cho trước có tối đa 10 chữ số.
• Số aᵢ (i > 0) là một số tự nhiên nhận được từ aᵢ₋₁ bằng cách viết tiếp thêm vào sau số aᵢ₋₁ các chữ số của aᵢ₋₁ nhưng theo thứ tự ngược lại.

Ví dụ: Với a₀ = 123 thì a₁ = 123321, a₂ = 123321123321, a₃ = 123321123321123321123321.

Yêu cầu: Với hai số tự nhiên n và m cho trước, hãy tìm chữ số thứ m của aₙ.

Dữ liệu: Vào từ tệp văn bản BAI3.INP:

• Dòng đầu chứa số a₀;
• Dòng thứ hai chứa hai số tự nhiên n và m (1 ≤ n ≤ 25, 1 ≤ m ≤ 10⁹).

Kết quả: Ghi ra tệp văn bản BAI3.OUT chữ số thứ m tìm được. Nếu không tìm được ghi -1.

Ví dụ:

BAI3.INP	BAI3.OUT	Giải thích
123 3 7	1	Có a₃ = 123321123321123321123321. Chữ số thứ 7 của a₃ là 1.

---

Chú ý:

• Cán bộ coi thi không giải thích gì thêm;
• Các tệp dữ liệu vào là đúng đắn không cần kiểm tra;
• Làm bài với các tên tệp đúng như quy định trong đề.