HSG lớp 9 Hà Nội 2014-2015

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 2014 - 2015
Môn thi: Tin học - Ngày thi: 09/04/2015
Thời gian làm bài: 150 phút
(Đề thi gồm 02 trang)

---

Câu 1. Phương trình (6 điểm)

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

Cho phương trình ax + by = c, với a, b, c là các số nguyên dương.

Yêu cầu: Tìm số lượng cặp (x, y), với x, y nguyên dương, là nghiệm của phương trình.

Dữ liệu: Vào từ tệp văn bản CAU1.INP một dòng duy nhất chứa ba số nguyên dương a, b, c, mỗi số không vượt quá 10⁹.

Kết quả: Ghi ra tệp văn bản CAU1.OUT số lượng các cặp nghiệm nguyên dương (x, y) của phương trình.

Ví dụ:

CAU1.INP	CAU1.OUT	Giải thích
2 4 20	4	Các cặp nghiệm nguyên dương của phương trình 2x + 4y = 20 là: (2, 4), (4, 3), (6, 2), (8, 1).

Câu 2. Chia nhóm (5 điểm)

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

Cho n số nguyên a₁, a₂, …, aₙ. Người ta muốn chia n số nguyên này thành các nhóm, trong mỗi nhóm hiệu của số lớn nhất và số nhỏ nhất không vượt quá số nguyên dương h cho trước.

Yêu cầu: Xác định số lượng nhóm ít nhất khi chia nhóm n số nguyên đã cho thỏa mãn điều kiện trên.

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

• Dòng đầu chứa hai số nguyên dương n và h, n ≤ 10³, h ≤ 10⁹;
• Trong n dòng tiếp theo, dòng thứ i (1 ≤ i ≤ n) chứa số nguyên aᵢ có giá trị tuyệt đối không vượt quá 10⁹.

Kết quả: Ghi ra tệp văn bản CAU2.OUT số lượng nhóm ít nhất tìm được.

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
6 3 -7 27 -5 26 28 -6	2	Có thể chia 6 số đã cho thành hai nhóm. Nhóm thứ nhất gồm các số thứ 1, thứ 3, thứ 6 và nhóm thứ hai là các số còn lại. Hai nhóm này đều có hiệu của số lớn nhất và số nhỏ nhất là 2 nhỏ hơn 3.

Câu 3. Tạo số (5 điểm)

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

Cho trước số nguyên dương t. Người ta tạo một số nguyên dương x bằng cách sau: trước hết, biểu diễn số t = p₁ · p₂ · … · pₖ, trong đó pᵢ (1 ≤ i ≤ k) là các số nguyên tố (k có thể bằng 1); tiếp theo viết các số p₁, p₂, …, pₖ theo một thứ tự nào đó liên tiếp nhau để nhận được số nguyên dương x.

Yêu cầu: Tìm giá trị lớn nhất của x.

Dữ liệu: Vào từ tệp văn bản CAU3.INP chứa số nguyên dương t không vượt quá 10⁹.

Kết quả: Ghi ra tệp văn bản CAU3.OUT giá trị x lớn nhất tìm được.

Ví dụ:

CAU3.INP	CAU3.OUT	Giải thích
476	72217	Có 476 = 2 · 2 · 7 · 17 nên số x lớn nhất là 72217

Câu 4. Bảng số (4 điểm)

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

Cho trước bảng số A gồm m hàng, n cột. Mỗi ô trong bảng số chứa một số nguyên dương gọi là giá trị của ô. Tất cả các ô (ít nhất là 2 ô) có cùng giá trị, kề cạnh hoặc kề đỉnh tạo thành một vùng số. Số lượng ô trong một vùng số gọi là diện tích của vùng số đó.

Yêu cầu: Tính số lượng vùng số có trong bảng A và diện tích của vùng số lớn nhất.

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

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

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

• Dòng đầu ghi số lượng các vùng số có trong bảng A;
• Dòng thứ hai ghi diện tích của vùng số lớn nhất.

Ví dụ:

CAU4.INP	CAU4.OUT	Giải thích
5 6 1 2 1 4 5 4 1 3 1 4 5 4 3 1 2 3 3 4 2 2 4 5 3 3 2 2 3 2 1 1	8 5	Có 8 vùng số gồm: 2 vùng số 1; 1 vùng số 2; 2 vùng số 3; 2 vùng số 4; 1 vùng số 5. Trong 8 vùng số trên, diện tích vùng số lớn nhất là 5.

---

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 đề.