HSG lớp 9 Hà Nội 2022-2023

SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI Năm học 2022 - 2023

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 MÔN TIN HỌC Ngày thi: 08/01/2023
Thời gian: 150 phút

---

Tổng quan đề thi

Bài	Tên bài	Tên file CT	File input	File output	Điểm
1	Thời gian	TG.*	TG.INP	TG.OUT	5
2	Mật mã	MM.*	MM.INP	MM.OUT	5
3	Trạm phát sóng	TPS.*	TPS.INP	TPS.OUT	4
4	Triển lãm	TL.*	TL.INP	TL.OUT	3
5	Dãy đẹp	DD.*	DD.INP	DD.OUT	3

Dấu * được thay thế bởi PAS, CPP hoặc PY tương ứng với ngôn ngữ lập trình sử dụng.

Bài 1. Thời gian (5 điểm)

Một trung tâm lái xe tổ chức thi sát hạch vào lúc 8 giờ 00 phút sáng ngày mai. Thời gian thực hiện bài sát hạch tối đa là 100 phút. Mỗi thí sinh có thể hoàn thành bài sát hạch trong thời gian khác nhau (tính theo phút). Đợt sát hạch gồm N thí sinh được đánh số từ 1 đến N. Thí sinh thứ i (1 ≤ i ≤ N) hoàn thành bài sát hạch trong Tᵢ phút. Trung tâm muốn biết thời điểm kết thúc bài sát hạch của mỗi thí sinh.

Dữ liệu vào từ file văn bản TG.INP:

• Dòng đầu tiên chứa một số nguyên N (1 ≤ N ≤ 20) là số lượng thí sinh;
• N dòng tiếp theo, dòng thứ i chứa một số nguyên Tᵢ là thời gian hoàn thành bài sát hạch của thí sinh thứ i (0 < Tᵢ ≤ 100, 1 ≤ i ≤ N).

Kết quả ghi ra file văn bản TG.OUT: Gồm N dòng, mỗi dòng là thời điểm bài thi kết thúc của từng thí sinh có cấu trúc giờ:phút (không chứa dấu cách). Nếu giờ và phút nhỏ hơn 10 thì ghi thêm chữ số 0 trên đầu, ví dụ 8 giờ 5 phút viết là 08:05.

Ví dụ:

TG.INP	TG.OUT
3 5 10 65	08:05 08:10 09:05

Bài 2. Mật mã (5 điểm)

Một mật thư chứa mật mã bí ẩn được tạo ra là một xâu kí tự gồm các chữ số và các kí tự in thường. Mật mã bí ẩn là số lượng các số nguyên phân biệt xuất hiện trong thư. Các số nguyên được viết không có các chữ số 0 đứng đầu.

Ví dụ, với mật thư as23dkrf23smk1asd23sam09aa9 chứa 3 số nguyên phân biệt 23, 1, 9. Nên mật mã là 3.

Yêu cầu: Hãy lập trình đưa ra mật mã bí ẩn.

Dữ liệu vào từ file văn bản MM.INP: Gồm một xâu (độ dài ≤ 100) gồm các chữ cái in thường và chữ số. Tất cả các số nguyên trong xâu có nhiều nhất 3 chữ số.

Kết quả ghi ra file văn bản MM.OUT: Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

MM.INP	MM.OUT
abc123abc2a3a1	4
as23dkrf23smk1asd23sam09aa9	3

Bài 3. Trạm phát sóng (4 điểm)

Các trạm thu phát sóng viễn thông của thành phố được đặt trên một đường tròn được chia thành 10⁶ điểm cách đều nhau theo chiều kim đồng hồ. Có một vị trí trên đó được tính là mốc 0. Có N trạm thu sóng được đánh thứ tự từ 1 đến N. Trạm thứ i có vị trí aᵢ (1 ≤ i ≤ N).

Thành phố dự kiến sẽ đầu tư K trạm phát sóng với phạm vi phát như nhau. Tuy nhiên, một trạm phát sóng với phạm vi phát càng dài thì chi phí càng cao nên thành phố cần tính toán để đầu tư các trạm phát sóng có phạm vi phát ngắn nhất. Và phải đảm bảo các trạm thu sóng đều nhận được tín hiệu.

Khi một trạm phát sóng có phạm vi phát là R thì các trạm thu sóng trong khoảng cách là R theo cả 2 chiều kim đồng hồ đều nhận được tín hiệu. Ví dụ, trạm phát sóng tại vị trí 3 với phạm vi phát 1 thì cả trạm thu sóng ở vị trí 2 và 4 đều nhận được tín hiệu.

Yêu cầu: Tìm phạm vi phát ngắn nhất của K trạm sóng sẽ đầu tư để N trạm thu sóng đều nhận được tín hiệu.

Dữ liệu vào từ file văn bản TPS.INP:

• Dòng đầu chứa số nguyên dương N (1 ≤ N ≤ 10³);
• N dòng tiếp theo, dòng thứ i chứa một số nguyên aᵢ, là vị trí trạm thu sóng thứ i (0 ≤ aᵢ ≤ 10⁶). Không có hai trạm nào cùng vị trí;
• Dòng cuối cùng chứa số nguyên K là số trạm phát sóng. Chú ý, vị trí trạm phát có thể được đặt cùng vị trí của một trạm thu nào đó.

Kết quả ghi ra file văn bản TPS.OUT: Số nguyên duy nhất là phạm vi phát sóng ngắn nhất của K trạm.

Ví dụ:

TPS.INP	TPS.OUT	Giải thích
4 5 1000 12345 987 2	498	Đặt một trạm phát sóng ở vị trí 503 và một trạm phát sóng ở vị trí 12340 có phạm vi phát sóng là 498.
2 1 999999 1	1	Đặt một trạm phát sóng ở vị trí 0 với phạm vi phát sóng là 1.

Bài 4. Triển lãm (3 điểm)

Bảo tàng thành phố có N bức tranh được đánh số thứ tự từ 1 đến N. Bức tranh thứ i (1 ≤ i ≤ N) có kích thước là Aᵢ và được định giá là Bᵢ.

Bảo tàng sẽ trưng bày các bức tranh và muốn chọn một số bức tranh trưng bày để thu được lợi nhuận lớn nhất thỏa mãn các tiêu chí:

1. Phải trưng bày ít nhất một bức tranh;
2. Chênh lệch về kích thước giữa các bức tranh được trưng bày càng nhỏ càng tốt;
3. Tổng giá trị các bức tranh được trưng bày là lớn nhất.

Gọi A_min là kích thước nhỏ nhất, A_max là kích thước lớn nhất, S là tổng giá trị của các bức tranh được lựa chọn trưng bày. Lợi nhuận của bảo tàng được tính theo công thức H = S − (A_max − A_min).

Yêu cầu: Hãy giúp giám đốc bảo tàng tìm H lớn nhất.

Dữ liệu vào từ file văn bản TL.INP:

• Dòng đầu tiên chứa số nguyên N (2 ≤ N ≤ 500 000) là số lượng các bức tranh;
• N dòng tiếp theo, dòng thứ i chứa hai số nguyên Aᵢ (1 ≤ Aᵢ ≤ 10¹⁵) và Bᵢ (1 ≤ Bᵢ ≤ 10⁹) là kích thước và định giá của bức tranh thứ i.

Kết quả: ghi ra file văn bản TL.OUT số nguyên H lớn nhất tìm được.

Ràng buộc:

• Có 25% số test ứng với 25% số điểm có n ≤ 16;
• 25% số test ứng với 25% số điểm có n ≤ 300;
• 25% số test ứng với 25% số điểm có n ≤ 5000;
• 25% số test còn lại không có ràng buộc gì thêm.

Ví dụ:

TL.INP	TL.OUT	Giải thích
3 2 3 9 2 4 5	6	Chọn các bức tranh là 1 và 3 thì: H = (3 + 5) − (4 − 2) = 6 là lớn nhất

Bài 5. Dãy đẹp (3 điểm)

Trong giờ số học, cô giáo đưa ra dãy A gồm N số nguyên dương từ 1 đến N. Cô giáo cho mỗi học sinh chọn một dãy con B gồm các phần tử liên tiếp của A. Dãy con B được gọi là dãy đẹp nếu khi sắp xếp B theo thứ tự tăng dần ta được một dãy số nguyên liên tiếp. Ví dụ, B = (2, 4, 3) là dãy đẹp trong khi B = (2, 3, 2) thì không.

Cô giáo yêu cầu cả lớp đếm xem có bao nhiêu dãy con đẹp của A. Cả lớp rất thích thú với bài toán này. Nhưng vì N có thể rất lớn nên việc đếm dãy con sẽ rất khó khăn.

Yêu cầu: Hãy giúp cả lớp đếm số lượng dãy con đẹp của A.

Dữ liệu vào từ file văn bản DD.INP:

• Dòng đầu tiên là số nguyên dương N (1 ≤ N ≤ 10⁵).
• Dòng tiếp theo chứa N số nguyên dương A₁, A₂, …, A_N (1 ≤ Aᵢ ≤ N, 1 ≤ i ≤ N).

Kết quả ghi ra file văn bản DD.OUT: Một số nguyên duy nhất là số lượng dãy con đẹp của A.

Ràng buộc:

• Có 30% số test ứng với 30% số điểm có N ≤ 200;
• 30% số test tiếp theo ứng với 30% số điểm có N ≤ 2000 và các phần tử của A đôi một phân biệt;
• 30% số test tiếp theo ứng với 30% số điểm có N ≤ 10⁵ và các phần tử của A đôi một phân biệt;
• 10% số test còn lại ứng với 10% số điểm có N ≤ 10⁵, 1 ≤ Aᵢ ≤ N, 1 ≤ i ≤ N.

Ví dụ:

DD.INP	DD.OUT	Giải thích
3 1 2 3	6	Có 6 dãy con đẹp là: (1), (2), (3), (1, 2), (2, 3), (1, 2, 3)