Kỳ thi chọn học sinh giỏi Lớp 12 cấp tỉnh môn Tin học - Sở GD&ĐT Đồng Tháp (Có đáp án)

(Bản scan)

Câu 3. (7,0 điểm) TUYẾN ĐÒ NGANG

Sông Tiển là một trong hai nhánh sông lớn của dòng sông MeKong. Trước đây, việc giao thông
qua lại giữa hai bờ sông chủ yếu bằng phà và các tuyến đò ngang. Từ năm 2000, cầu Mỹ Thuận đã được
đưa vào sử dụng và sắp tới đây sẽ tiếp tục khánh thành cầu Cao Lãnh nối liền hai bờ sông Tiền. Có thể
nói, những công trình này cùng với cầu Cần Thơ và cầu Vàm Cống (cũng sắp hoàn thành) đã góp phần rất
lớn trong việc phát triển kinh tế của vùng ĐBSCL, kết nối vùng ĐBSCL gần hơn với TP.HCM và các tỉnh
miền Đông Nam bộ. Mặc dù vậy, chúng ta cũng không thể phủ nhận vai trò của những tuyên đò ngang
hiện nay vì sự tiện lợi của nó thay vì phải đi vòng những đoạn đường xa để qua sông bằng cầu.

Hiện tại, dọc theo sông Tiển có N tuyến đò ngang đang hoạt động, mỗi tuyến đò đi từ một bến đò
ở bờ Bắc sông Tiền sang một bến ở bờ Nam sông Tiên và ngược lại. Các bến đò ở mỗi bờ được đánh số
từ 1 đến N theo thứ tự từ thượng nguồn xuống hạ nguồn. Biết rằng, nếu tuyến đò xuất phát từ bến đò ¡ ở
bờ Bắc thì sẽ đi sang bến đò a; ở bờ Nam (i=1..N, a, = 1..N, a; # a¡ Vizj). Vấn đề phát sinh là giữa một số
tuyến đò có hành trình khi sang sông bị giao cắt nhau và như vậy có thê không an toàn cho hành khách vì
có thể xảy ra tại nạn va chạm trên sông. Chính vì vậy chính quyền địa phương dự định sẽ cho dừng hoạt
động một số tuyến đò, chỉ giữ lại những tuyển đò mà hành trình của nó không giao cắt với hành trình của
những tuyến khác được giữ lại.

Yêu cầu: Hãy tìm một phương án dừng hoạt động một số ít nhất các tuyến đò sao cho những
tuyến đò hoạt động còn lại có hành trình không giao cắt nhau.

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

Dòng thứ nhất ghi số nguyên dươngN
Dòng thứ hai ghi N số nguyên đương ai, 4;, ..., ay. Giữa các số cách nhau một khoảng cách.