Đề tin tham khảo.

Kỳ thi chọn học sinh giỏi tỉnh lớp 12
Năm học 2006 – 2007
Môn thi: Tin học
Thời gian 180 phút ( không kể thời gian giao đề)

Bài 1: Chúc tết
An có N người bạn, được đánh số thứ tự từ 1,2..,N. An dùng một ngày để đi chúc tết các bạn của mình. Để chắc chắn, hôm trước An đã gọi điện cho tất cả các bạn để biết được khoảng thời gian mà người đó có thể ở nhà tiếp mình. Giả sử người bạn thứ I ở nhà trong khoảng thời gian Ai đến Bi ( i=1,2,..,N). Thời gian cần thiết cho mỗi cuộc gặp là T và thời gian để chuẩn bị từ một cuộc gặp đến cuộc gặp kế tiếp là G.
Bài toán đặt ra là: hãy giúp An đưa ra một lộ trình chúc tết, đẻ An gặp được nhều bạn nhất.
Dự liệu vào cho từ File văn bản CHUCTET.inp cs cấu trúc như sau:
+ Dòng đầu tiên ghi số N.(0<1<=100)
+ Dòng thứ i trong N dòng tiếp theo ghi 2 số thực Ai,Bi ( 8<=Ai,Bi<=21) là thời gian mà người bạn thứ i có thể ở nhà tiếp An.
+ Dòng tiếp theo ghi 2 số thực T, G theo thứ tự là thời gian cần thiết cho một cuộc gặp và thời gian chuản bị cho 2 cuộc gặp liên tiếp.
Giả tiết rằng các giá trị thời gian đều viết dưới dạng thập phân theo đơn vị giờ( ví dụ 10.5 có nghĩa là 10 giờ rưỡi).
Kết quả ghi ra File văn bản CHUCTET.out có cấu trúc nhu sau:
+ Dòng đầu tiên ghi số K là số người mà An đến chúc tết.
+ K dòng tiếp theo,mỗi dòng ghi 2 số, số đầu là số hiệu người bạn được thăm, số thứ 2 là thời điểm An gặp người bạn này.
Ví dụ
CHUCTET.inp
CHUCTET.out

20
10.5 12.6
15.5 16.6
14.0 14.1
17.5 21.2
15.0 16.1
10.5 10.6
19.0 21.0
10.5 13.6
12.5 12.6
11.5 13.6
12.5 15.6
16.0 18.1
13.5 14.6
12.5 17.6
13.0 13.1
18.5 21
9.0 13.1
10.5 11.6
10.5 12.6
18.0 21.0
0.5 0.1
16
17 9.0
1 10.5
18 11.1
19 11.7
8 12.3
10 12.9
11 13.5
13 14.1
5 15
2 15.6
12 16.2
14 16.8
4 17.5
7 19.0
16 19.6
20 20.2


Bài 2 Tân trang xe.
Để phục vụ cho lễ hội người ta cần tân trang N xe để đón khách.Các xe được đánh số thứ tự 1,2,..,N và số thứ tự của xe cũng được gọi là số hiệu của xe. Mỗi xe tân trang cần phải cần phải trải qua 2 công đoạn đánh gỉ sau đó sơn. Thời gian đánh gỉ xe i là Ti và thời gian để sơn là Di ( i=1,2..,N). Vì thời gian không còn nhiều. Bạn hãy tìm giúp cho ban tổ chức một thứ tự tân trang N xe sao cho thời gian hoàn thành nhanh nhất. Biết rằng mỗi công đoạn khi xong xe này mới chuyển sang xe khác.
Dự liệu vào cho từ File văn bản XE.inp.
+ dòng đầu tiên ghi số N ( 1+ Dòng thứ