Kỳ thi chọn học sinh giỏi Quốc gia THPT môn Tin học

(Bản scan)

Bài 1. Con đường Tùng-Trúc (6 điểm)
Địa điểm du lịch Dailai nỗi tiếng với con đường Tùng-Trúc. Đó là một con đường dài và thẳng.
dọc bên đường người ta trồng rất nhiều cây tùng và cây trúc. Với mục đích tạo điểm nhân cho con
đường, Ban quản lý khu du lịch muôn chọn một đoạn đường mà đọc theo nó có ít nhất a cây tùng
và có ít nhất b cây trúc đề trang trí. Sau khi khảo sát, Ban quản lý ghi nhận được vị trí của từng cây
tùng và cây trúc. Trên con đường có tất cả n cây, không có hai cây nào ở cùng một vị trí. Cây thứ ¡
ở vị trí có khoảng cách đến vị trí bắt đầu con đường là đ, (¡ = 1,2,..., n). Với kinh phí có hạn, Bạn
quản lý muốn chọn đoạn đường thỏa mãn điều kiện đã nêu với độ dài là ngăn nhất.
Yêu cầu: Cho z, b và vị trí của ø cây. Hãy tìm đoạn đường có độ dài ngắn nhất mà dọc theo đó có
ít nhất a cây tùng và có ít nhất ö cây trúc.
Dữ liệu: Vào từ file văn bản MINROAD.INE:
Dòng dầu chứa 3 số nguyên dương n. a, b (a + b< n):
Dòng thứ ¿ trong ø dòng tiếp theo, mỗi đỏng chứa hai số nguyên dương đ, (đ, < 10”) và &„
trong đó đ, là khoảng cách của cây tính từ vị trí băt đâu của con đường. k, = Ï nêu là cây
tùng, #, = 2 nêu lả cây trúc.
Các số trên cùng một đòng được ghỉ cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản MINROAD.OUT một số nguyên là độ dài đoạn đường ngắn nhất tìm
được, quy ước ghi số -1 nêu không tôn tại đoạn đường nào thỏa mãn điêu kiện đặt ra.