HSG lớp 9 Hà Nội 2017-2018

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

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

Câu 1. Tìm số đặc biệt (6 điểm)

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

Một số nguyên dương được gọi là đặc biệt nếu tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố. Ví dụ, 12 là số đặc biệt vì 1² + 2² = 5 là số nguyên tố.

Yêu cầu: Cho số nguyên dương n. Hãy tìm số đặc biệt nhỏ nhất lớn hơn n.

Dữ liệu: Vào từ tệp văn bản CAU1.INP chứa số nguyên dương n (1 ≤ n ≤ 10⁹).

Kết quả: Ghi vào tệp văn bản CAU1.OUT số đặc biệt nhỏ nhất lớn hơn n.

Ví dụ:

CAU1.INP	CAU1.OUT	Giải thích
`11`	`12`	1² + 2² = 5 là số nguyên tố

Câu 2. Tặng quà (5 điểm)

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

Để động viên khích lệ học sinh tham gia dự thi học sinh giỏi năm nay, trường ITS có chuẩn bị n phần quà cho n thí sinh dự thi. Trên hộp quà thứ i có ghi số nguyên aᵢ, các số aᵢ đôi một khác nhau (1 ≤ i ≤ n). Sau khi tặng quà cho các thí sinh, trường sẽ có thêm những cặp quà đặc biệt cho những cặp thí sinh có cặp số trên hộp quà là (aᵢ, aⱼ) (i ≠ j, 1 ≤ i ≤ n, 1 ≤ j ≤ n) mà aᵢ + aⱼ = 0.

Yêu cầu: Hãy cho biết trường phải chuẩn bị thêm bao nhiêu cặp quà đặc biệt.

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

Dòng thứ nhất chứa số nguyên dương n (1 < n ≤ 10⁶);
Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ đôi một khác nhau (|aᵢ| ≤ 10⁵, 1 ≤ i ≤ n).

Kết quả: Ghi ra tệp văn bản CAU2.OUT số lượng cặp quà đặc biệt.

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
`7` `6 -3 0 1 -1 3 2`	`2`	Có hai cặp có tổng bằng 0: -3 + 3 = 0 -1 + 1 = 0

Câu 3. Xâu chung lớn nhất (5 điểm)

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

Cho hai xâu X và Y có độ dài tối đa mỗi xâu không quá 500 kí tự, bao gồm các chữ cái và các chữ số.

Yêu cầu: Hãy tìm xâu Z là xâu con chung liên tiếp của hai xâu X và Y gồm toàn chữ số tạo thành một số có giá trị lớn nhất.

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

Dòng thứ nhất chứa xâu X;
Dòng thứ hai chứa xâu Y.

Kết quả: Ghi ra tệp văn bản CAU3.OUT xâu Z tìm được.

Ví dụ:

CAU3.INP	CAU3.OUT	Giải thích
`ab123abcba57` `cba12abcbad23`	`23`	- Các xâu con gồm toàn chữ số của xâu X là: 1, 12, 123, 2, 23, 3, 5, 57, 7 - Các xâu con gồm toàn chữ số của xâu Y là: 1, 12, 2, 2, 23, 3 - Xâu con chung liên tiếp gồm toàn chữ số có giá trị lớn nhất: 23

Câu 4. Trò chơi với tấm bìa (4 điểm)

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

Tùng có m × n tấm bìa hình vuông được xếp thành một hình chữ nhật có m dòng và n cột. Tấm bìa ở dòng thứ i và cột thứ j có ghi một số nguyên dương aᵢ,ⱼ (1 ≤ i ≤ m, 1 ≤ j ≤ n). Tùng đố An lật úp các tấm bìa như sau: khi lật úp tấm bìa có ghi số nguyên dương aᵢ,ⱼ thì tất cả các tấm bìa có ghi số bằng số aᵢ,ⱼ cũng được lật úp và An có nhiều nhất k lần lật úp các tấm bìa.

Ví dụ:


1	2	1	3	1	1
6	1	4	1	4	3
1	2	1	4	1	1

Với hình chữ nhật như hình trên m = 3, n = 6, k = 2 thì An có thể lật các tấm bìa như sau:

Lật úp tấm bìa có ghi số nguyên dương 1 và tấm bìa có ghi số nguyên dương 3 sẽ có 12 tấm bìa được lật úp.
Lật úp tấm bìa có ghi số nguyên dương 1 và tấm bìa có ghi số nguyên dương 4 sẽ có 13 tấm bìa được lật úp.

Yêu cầu: Hãy giúp An tìm cách lật úp các tấm bìa không quá k lần sao cho số tấm bìa được lật úp là nhiều nhất.

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

Dòng thứ nhất chứa ba số nguyên dương m, n, k (1 < m ≤ 300, 1 < n ≤ 300, 1 ≤ k ≤ m × n);
m dòng tiếp theo, mỗi dòng ghi n số nguyên dương aᵢ,ⱼ là số ghi trên tấm bìa ở dòng thứ i và cột thứ j (0 < aᵢ,ⱼ ≤ 10⁵, 1 ≤ i ≤ m, 1 ≤ j ≤ n).

Kết quả: Ghi ra tệp văn bản CAU4.OUT số lượng tấm bìa nhiều nhất An lật úp được.

Ví dụ:

CAU4.INP	CAU4.OUT
`3 6 2` `1 2 1 3 1 1` `6 1 4 1 4 3` `1 2 1 4 1 1`	`13`

Câu 4 (phiên bản khác). Sơn tường chung cư

Thành phố ABC có một khu đô thị gồm nhiều khối chung cư cao tầng được mô tả trong bản đồ hình chữ nhật gồm m dòng và n cột. Các dòng được đánh số từ 1 đến m và các cột được đánh số từ 1 đến n. Ô ở dòng thứ i và cột thứ j ghi một số nguyên dương aᵢ,ⱼ mô tả số tầng của một khối chung cư ở hàng thứ i và cột j. Một khối chung cư được định nghĩa là một tập hợp các ô có đáy tạo thành một miền gồm những ô vuông kề cạnh có giá trị lớn hơn 0.

Để chỉnh trang khu đô thị người ta muốn sơn toàn bộ các bức tường xung quanh (không cần phải sơn mái chung cư) tất cả các khối chung cư bằng một loại sơn mới bền và đẹp hơn. Ban quản lý khu đô thị muốn xác định số lượng các khối chung cư, tổng số diện tích phải sơn, diện tích của khối chung cư phải sơn lớn nhất (mỗi mặt của một tầng được tính là một đơn vị diện tích).

Yêu cầu: Với bản đồ trên, hãy giúp ban quản lý khu đô thị xác định số lượng các khối chung cư, tổng số diện tích phải sơn, diện tích của khối chung cư phải sơn lớn nhất.

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

Dòng thứ nhất chứa hai số nguyên dương m và n (1 < m ≤ 500, 1 < n ≤ 500);
m dòng tiếp theo, mỗi dòng ghi n số nguyên aᵢ,ⱼ là số ghi trên ô vuông ở dòng thứ i và cột thứ j (0 ≤ aᵢ,ⱼ ≤ 10³, 1 ≤ i ≤ m, 1 ≤ j ≤ n).

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

Dòng thứ nhất ghi số lượng các khối chung cư;
Dòng thứ hai ghi tổng số diện tích cần sơn;
Dòng thứ ba ghi diện tích khối chung cư cần sơn lớn nhất.

Ví dụ:

CAU4.INP	CAU4.OUT	Giải thích
`4 5` `0 0 0 2 0` `0 0 0 1 0` `0 1 3 0 0` `0 0 0 0 0`	`2` `24` `14`	- Có 2 khối chung cư; - Khối thứ nhất có số mặt sơn là: 2 + 2 + 2 + 1 + 1 + 1 + 1 = 10; - Khối thứ hai có số mặt sơn là: 1 + 1 + 1 + 2 + 3 + 3 + 3 = 14; - Tổng diện tích cần sơn là: 24; - Diện tích khối nhà cần sơn lớn nhất là: 14.

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 đề, trong đó dấu * là phần mở rộng mặc định theo ngôn ngữ lập trình mà thí sinh sử dụng (ví dụ: CAU1.PAS, CAU1.CPP, …).

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English