HSG lớp 9 Đồng Tháp 2018-2019

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH ĐỒNG THÁP ĐỀ CHÍNH THỨC
(Đề gồm có 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP TỈNH Năm học 2018 - 2019
Môn: Tin học - Ngày thi: 17/3/2019
Thời gian làm bài: 150 phút, không kể thời gian phát đề

---

Tổng quan đề thi

Tên bài	Tên tệp bài làm	Tên tệp dữ liệu vào	Tên tệp kết quả
Bài 1. Văn nghệ	BL1.*	VANNGHE.INP	VANNGHE.OUT
Bài 2. Làng hoa	BL2.*	LANGHOA.INP	LANGHOA.OUT
Bài 3. Đoạn đường đẹp nhất	BL3.*	DDUONG.INP	DDUONG.OUT

Ghi chú: dấu * đại diện cho phần mở rộng, tuỳ theo ngôn ngữ lập trình có thể là PAS hoặc CPP. Thời gian thực hiện chương trình không quá 1 giây, bộ nhớ không quá 1024MB.

Bài 1. Văn nghệ (6,0 điểm)

Nhân dịp xuân về, đội văn nghệ của Nhà văn hoá thiếu nhi được cử đi biểu diễn giao lưu ở các phường trong thành phố. Đội văn nghệ có n bạn học sinh nam và m bạn học sinh nữ được chia thành các tổ, mỗi tổ sẽ đi phục vụ văn nghệ cho người dân ở các phường khác nhau. Biết rằng: số lượng học sinh nam và số lượng học sinh nữ phải được chia đều giữa các tổ và sau khi chia tổ, mỗi học sinh đều thuộc một tổ.

Yêu cầu: Em hãy cho biết đội văn nghệ có thể chia nhiều nhất bao nhiêu tổ? Mỗi tổ có bao nhiêu học nam và bao nhiêu học sinh nữ?

Dữ liệu vào: Cho từ tệp văn bản VANNGHE.INP chỉ có một dòng chứa hai số nguyên n và m, giữa hai số cách nhau một khoảng trắng (1 ≤ n, m ≤ 10¹⁵).

Kết quả: Ghi vào tệp văn bản VANNGHE.OUT gồm:

• Dòng thứ nhất ghi một số nguyên là số lượng tổ tối đa có thể chia được.
• Dòng thứ hai ghi hai số a, b tương ứng là số học sinh nam và số học sinh nữ của mỗi tổ, giữa hai số cách nhau một khoảng trắng.

Ví dụ:

VANNGHE.INP	VANNGHE.OUT
48 72	24 2 3

Ràng buộc:

• Có 70% số test tương ứng 70% số điểm có 1 ≤ n, m ≤ 10⁶.
• Có 30% số test tương ứng 30% số điểm có 10⁶ < n, m ≤ 10¹⁵.

Bài 2. Làng hoa (7,0 điểm)

Dọc theo tuyến đường vào Làng hoa Sa Đéc có n điểm tham quan đánh số từ 1 đến n theo hướng từ đầu đường vào làng hoa đến cuối đường. Để phục vụ du khách, ban quản lý đã trang bị các xe điện để đưa đón khách. Các xe điện được chia thành hai tuyến, tuyến thứ nhất chạy theo hướng từ đầu đường đến cuối đường và tuyến thứ hai chạy theo hướng ngược lại. Khi xe điện chạy đến điểm dừng cuối cùng của tuyến thì tất cả du khách phải xuống xe để xe vào nhà ga nạp lại điện. Để tránh quá tải tại các điểm tham quan cũng như tránh ùn tắc giao thông, mỗi tuyến xe điện chỉ dừng lại tại một số điểm tham quan để đón trả khách.

Yêu cầu: Có k du khách hiện đang ở điểm tham quan số 1 và đã biết thông tin về các điểm dừng đón trả khách của mỗi tuyến xe điện. Du khách thứ i muốn di chuyển đến điểm tham quan sᵢ. Hãy cho biết mỗi du khách có thể di chuyển đến điểm tham quan mong muốn bằng cách sử dụng xe điện hay phải sử dụng phương tiện giao thông khác?

Dữ liệu vào: Cho từ tệp văn bản LANGHOA.INP có dạng:

• Dòng thứ nhất ghi hai số nguyên dương n, k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁵).
• Dòng thứ hai ghi n số nguyên a₁, a₂, …, aₙ, trong đó aᵢ = 1 nếu tuyến xe điện thứ nhất có dừng lại để đón trả khách tại điểm tham quan thứ i và aᵢ = 0 nếu xe điện không dừng lại tại điểm tham quan thứ i (i = 1..n).
• Dòng thứ ba ghi n số nguyên b₁, b₂, …, bₙ, trong đó bᵢ = 1 nếu tuyến xe điện thứ hai có dừng lại để đón trả khách tại điểm tham quan thứ i và bᵢ = 0 nếu xe điện không dừng lại tại điểm tham quan thứ i (i = 1..n).
• Dòng thứ tư ghi k số nguyên dương s₁, s₂, …, sₖ trong đó sᵢ là điểm tham quan mà du khách thứ i muốn di chuyển đến (1 ≤ sᵢ ≤ n, i = 1..k).

Các số trên cùng một dòng ghi cách nhau ít nhất một khoảng trống.

Kết quả: Ghi vào tệp văn bản LANGHOA.OUT gồm một dòng ghi k số nguyên - số thứ i bằng 1 nếu du khách thứ i có thể di chuyển bằng xe điện đến điểm tham quan sᵢ và bằng 0 nếu du khách thứ i không thể di chuyển bằng xe điện đến điểm tham quan sᵢ.

Ví dụ:

LANGHOA.INP	LANGHOA.OUT
6 2 1 0 1 1 0 1 1 1 0 1 1 0 2 5	1 0

Giải thích:

• Du khách thứ nhất có thể đến điểm tham quan số 2 bằng cách đi theo tuyến thứ nhất đến điểm tham quan số 4 thì xuống xe và chuyển sang tuyến thứ hai đi ngược về điểm số 2.
• Du khách thứ hai không thể dùng xe điện để đi đến điểm tham quan số 5.

Ràng buộc:

• Có 70% số test tương ứng 70% số điểm có giá trị k ≤ 100.
• Có 30% số test tương ứng 30% số điểm có giá trị k ≤ 10⁵.

Bài 3. Đoạn đường đẹp nhất (7,0 điểm)

Trong thời gian vừa qua, người dân ở thành phố XYZ đã vui mừng chào đón sự xuất hiện của con đường ven biển, con đường được đầu tư rất nhiều kinh phí làm đường và xây dựng các tòa nhà đẹp nằm ở cùng một phía của con đường, con đường này được coi là con đường có cảnh quang đẹp nhất hành tinh. Con đường có n tòa nhà, được đánh thứ tự từ 1 đến n, tính từ đầu đường, tòa nhà thứ i có độ cao là hᵢ (i = 1..n). Theo các chuyên gia kiến trúc và thẩm mĩ, đoạn đường đẹp nhất là đoạn đường mà ở đó có độ cao trung bình của các tòa nhà đúng bằng k.

Yêu cầu: Em hãy tìm đoạn đường có các tòa nhà liên tiếp nhau nhiều nhất sao cho đoạn đường này là đoạn đường đẹp nhất (độ cao trung bình của các tòa nhà đúng bằng k).

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

• Dòng thứ nhất ghi hai số nguyên n và k (1 ≤ n ≤ 10⁵; 0 ≤ k ≤ 10⁹).
• Dòng thứ hai ghi n số nguyên h₁, h₂, …, hₙ (0 < hᵢ ≤ 10⁹; i = 1..n).

Các số trên cùng một dòng ghi cách nhau ít nhất một khoảng trống.

Kết quả: Ghi vào tệp văn bản DDUONG.OUT gồm:

• Dòng thứ nhất ghi một số nguyên u là chỉ số bắt đầu của toà nhà thuộc đoạn đường đẹp nhất tìm được, nếu có nhiều đáp án thì ghi chỉ số u nhỏ nhất.
• Dòng thứ hai ghi một số nguyên v là số lượng toà nhà thuộc đoạn đường tìm được. Nếu không có đoạn đường nào đẹp nhất thì ghi ra duy nhất số 0.

Ví dụ:

DDUONG.INP	DDUONG.OUT
4 5 2 4 5 6	2 3

Ràng buộc:

• Có 50% số test tương ứng 50% số điểm có 1 < n ≤ 2×10².
• Có 30% số test tương ứng 30% số điểm có 2×10² < n ≤ 2×10³.
• Có 20% số test tương ứng 20% số điểm có 2×10³ < n ≤ 10⁵.