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

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 2018 - 2019
Môn thi: Tin học - Ngày thi: 10 tháng 01 năm 2019
Thời gian làm bài: 150 phút
(Đề thi gồm 02 trang)

---

Câu 1. Cặp số (6 điểm)

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

Cho trước ba số nguyên dương a, b và k. Hai số nguyên dương x và y gọi là cặp số đặc biệt nếu thỏa mãn a ≤ x² ≤ b, a ≤ y³ ≤ b và |x² − y³| ≤ k.

Yêu cầu: Tìm số lượng các cặp số đặc biệt.

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

Kết quả: Ghi ra tệp văn bản CAU1.OUT một số nguyên duy nhất là số lượng các cặp số đặc biệt tìm được.

Ví dụ:

CAU1.INP	CAU1.OUT	Giải thích
1 30 2	3	Có ba cặp số đặc biệt: (1, 1); (3, 2) và (5, 3).

Câu 2. Biến đổi khí hậu (5 điểm)

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

Để nghiên cứu về tác động của biến đổi khí hậu, An tiến hành một thí nghiệm với kịch bản như sau: An chọn một số vị trí trên bản đồ và đánh số từ 1 cho đến hết. Ban đầu, độ cao so với mực nước biển của tất cả các vị trí là 0. An sẽ thực hiện n tác động biến đổi khí hậu được đánh số từ 1 đến n. Tác động thứ i (1 ≤ i ≤ n) sẽ làm thay đổi độ cao của các vị trí có số hiệu từ l_i đến r_i lần lượt theo quy tắc: vị trí l_i sẽ tăng độ cao thêm x_i, vị trí l_i + 1 sẽ giảm bớt độ cao x_i, vị trí l_i + 2 sẽ tăng độ cao thêm x_i và tiếp tục cho đến vị trí r_i.

Yêu cầu: Hãy giúp An xác định độ cao của m vị trí p₁, p₂, …, p_m sau khi thực hiện n tác động.

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

• Dòng thứ nhất chứa hai số nguyên dương m và n (m ≤ 10³, n ≤ 10³);
• Trong m dòng tiếp theo, dòng thứ i chứa số nguyên dương p_i (p_i ≤ 10⁹, 1 ≤ i ≤ m);
• Trong n dòng tiếp theo, dòng thứ i chứa 3 số nguyên dương l_i, r_i và x_i (l_i ≤ r_i ≤ 10⁹, x_i ≤ 10³, 1 ≤ i ≤ n).

Kết quả: Ghi ra tệp văn bản CAU2.OUT gồm m dòng, dòng thứ i ghi độ cao của vị trí p_i (1 ≤ i ≤ m) tìm được.

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
5 2 1 3 6 7 8 1 6 7 3 7 2	7 9 -9 2 0	- Sau tác động thứ 1: các vị trí 1 và 3 có độ cao là 7, vị trí 6 có độ cao -7, các vị trí 7 và 8 giữ nguyên độ cao 0. - Sau tác động thứ 2: vị trí 1 giữ nguyên độ cao 7, vị trí 3 có độ cao 9, vị trí 6 có độ cao -9; vị trí 7 có độ cao là 2, vị trí 8 giữ nguyên độ cao 0.

Câu 3. Chọn xâu (5 điểm)

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

Cho hai xâu kí tự S₁ và S₂ chỉ gồm các chữ cái tiếng Anh in thường. Thực hiện xóa từ xâu S₁ một số kí tự và giữ nguyên vị trí tương đối của các kí tự còn lại nhận được xâu S. Nếu xâu S cũng có thể nhận được bằng cách xóa từ xâu S₂ một số kí tự và giữ nguyên vị trí tương đối của các kí tự còn lại thì xâu S gọi là xâu chấp nhận được.

Yêu cầu: Tìm xâu S chấp nhận được có thứ tự từ điển lớn nhất.

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

• Dòng thứ nhất chứa xâu S₁ khác rỗng có độ dài không quá 250;
• Dòng thứ hai chứa xâu S₂ khác rỗng có độ dài không quá 250.

Kết quả: Ghi ra tệp văn bản CAU3.OUT xâu S tìm được. Nếu không có xâu S thỏa mãn thì ghi số -1.

Ví dụ:

CAU3.INP	CAU3.OUT	Giải thích
aecaeca abcda	ca	Các xâu chấp nhận được của hai xâu đã cho theo thứ tự từ điển gồm: a, aa, ac, aca, c, ca. Xâu cần tìm là S = ca.

Câu 4. Hình vuông con (4 điểm)

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

Một bảng hình chữ nhật được chia thành lưới ô vuông đơn vị kích thước m × n. Các hàng của bảng được đánh số từ 1 đến m, từ trên xuống dưới. Các cột của bảng được đánh số từ 1 đến n, từ trái qua phải. Ô nằm trên hàng i, cột j của bảng được gọi là ô (i, j) và có ghi giá trị a_i,_j (1 ≤ i ≤ m, 1 ≤ j ≤ n). Một hình vuông con của bảng là hình vuông chiếm chọn một số ô của bảng.

Yêu cầu: Với số nguyên dương k cho trước, hãy chọn ra một hình vuông con kích thước k × k sao cho giá trị của số nhỏ nhất trong hình vuông con là lớn 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 ≤ 1000, 1 < n ≤ 1000, k ≤ m, k ≤ n);
• Trong m dòng tiếp theo, mỗi dòng chứa n số nguyên dương a_i,_j là số ghi trên ô ở dòng thứ i và cột thứ j (a_i,_j ≤ 10⁶, 1 ≤ i ≤ m, 1 ≤ j ≤ n).

Kết quả: Ghi ra tệp văn bản CAU4.OUT một số nguyên duy nhất là giá trị của số nhỏ nhất trong hình vuông thỏa mãn điều kiện.

Ví dụ:

CAU4.INP	CAU4.OUT	Giải thích
5 5 2 1 11 2 3 3 9 9 2 3 3 2 2 2 2 2 1 2 2 5 6 4 10 2 7 8	5	Hình vuông con kích thước 2 × 2: 5 6 7 8 có giá trị của số nhỏ nhất là 5 thỏa mãn điều kiện.

---

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, …).