KỲ THI OLYMPIC TRUYỀN THỐNG 30/4
LẦN THỨ XIII TẠI THÀNH PHỐ HUẾ
ĐỀ THI MÔN TIN HỌC
Thời gian làm bài 180’
Khối 11
Tổng quan đề thi:
Tên bài Phân công công việc Khu vui chơi Xe buýt
File bài làm Bl1.pas Bl2.pas Bl3.pas
Dữ liệu vào CV.INP VC.INP XB.INP
Dữ liệu ra CV.OUT VC.OUT XB.OUT
Giới hạn 2giây 2giây 2giây
Chú ý: Bài thi được làm trên ngôn ngữ lập trình Turbo Pascal
Đề thi gồm có 3 trang
BÀI 1: Phân công công việc
Có n công việc (n ≤ 100) lần lượt được thực hiện trên 1 máy tính, mỗi việc đòi hỏi
đúng 1 giờ chạy trên máy. Với mỗi việc ta biết thời hạn chậm nhất có thể để hoàn thành
và tiền thù lao thu được nếu thực hiện đúng thời hạn.
Yêu cầu: Chỉ có 1 máy tính, bạn hãy đưa ra một kế hoạch thực hiện trên máy sao
cho tổng số tiền thù lao thu được là lớn nhất.
Chú ý: Bạn không nhất thiết phải hoàn thành tất cả các công việc trên.
Dữ liệu vào: Được ghi trong file: CV.INP có cấu trúc:
• Dòng đầu tiên chứa số nguyên dương n ≤ 100.
• N dòng tiếp theo mỗi dòng chứa cặp số nguyên dương a
i
, b
i
(i chạy từ 1 đến n)
mỗi số cách nhau một khoảng trắng. Với a
i
(1 ≤ a
i

, …, A
m
. Vì các du khách muốn biết trước được tổng chiều dài hành trình mà
họ phải đi qua nên ban quản lý quyết định thuê bạn để tính độ dài này. Biết rằng độ dài
hành trình bằng tổng độ dài các đường đi trên hành trình đó.
Dữ liệu vào: Được ghi trong file văn bản VC.INP có cấu trúc:
• Dòng đầu tiên chứa 2 số nguyên dương N và M với N<=250; M<=N.
• N-1 dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương u, v mô tả có con đường
nối 2 địa điểm u và v.
• Dòng cuối cùng gồm M số lần lượt là M địa điểm trên hành trình
Dữ liệu ra: Kết quả ghi vào file văn bản VC.OUT chỉ có 1 số là tổng độ dài hành
trình
Ví dụ:

VC.INP VC.OUT
8 5
1 4
1 2
3 2
3 8
1 5
3 6
2 7
4 8 5 6 7
15
BÀI 3: Xe buýt
Trên một tuyến đường ở thành phố du lịch nổi tiếng X có ô tô buýt công cộng phục
vụ việc đi lại của du khách. Bến xe buýt có ở từng km của tuyến đường. Mỗi lần đi qua
bến xe đều đỗ lại cho khách lên xuống. Mỗi bến đều có xe xuất phát từ nó, nhưng mỗi xe
chỉ chạy không quá b km kể từ bến xuất phát của nó. Hành khách khi đi xe sẽ phải trả