CHUẨN BỊ SVOI 2010ĐỂ CHUẨN BỊ CHO KỲ THI OLYMPIC SINH VIÊN 2010...

bài 3. - Đề thi olympic tin học sinh viên lần thứ 19 - 1
Tin học Đề thi olympic tin học sinh viên lần thứ 19 - 1

Bài 3. Chuẩn bị SVOI 2010

Để chuẩn bị cho kỳ thi Olympic Sinh viên 2010, Ban huấn luyện đội tuyển Tin học trường

đại học D giao cho mỗi thành viên đội tuyển n bài tập, các bài tập được đánh số từ 1 tới n.

Thông thường, để giải được một bài tập sinh viên cần phải được trang bị một số kiến thức

nào đó về thuật toán và cấu trúc dữ liệu và sau khi giải xong bài tập đó sinh viên nhận thêm

được một số kiến thức mới về hai lĩnh vực đó. Để giải bài tập thứ i sinh viên cần có chỉ số

kiến thức tối thiểu về thuật toán và cấu trúc dữ liệu được đánh giá tương ứng bởi hai số

nguyên không âm a

i

, b

i

và sau khi giải xong bài thứ i kiến thức về thuật toán và cấu trúc dữ

diệu được tăng thêm một lượng c

i

và d

i

. Sinh viên Tuấn rất chăm chỉ trong quá trình tập

huấn và rất mong muốn giải được càng nhiều bài tập càng tốt. Hiện tại Tuấn có chỉ số kiến

thức về thuật toán là T và chỉ số kiến thức về cấu trúc dữ liệu P.

Yêu cầu: Hãy tính số lượng nhiều nhất S các bài tập mà Tuấn có thể giải được.

Dữ liệu: Vào từ file văn bản SVOI.INP có n+1 dòng, trong đó dòng đầu chứa ba số n, T và

P (0 <n ≤ 1000; 0 ≤ T, P ≤ 10

6

). Dòng thứ i trong n dòng tiếp theo chứa bốn số nguyên

không âm a

i

, b

i

, c

i

và d

i

(0 ≤ a

i

, b

i

, c

i

, d

i

≤ 10

6

).

Các số trên cùng một dòng cách nhau bởi ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản SVOI.OUT số lượng S các bài tập mà Tuấn giải được.

Ví dụ:

SVOI.INP SVOI.OUT Giải thích

5 1 3

5 Một phương án làm được cả

2 1 1 0

5 bài đó là lần lượt làm các

1 0 1 0

bài: 2, 1, 5, 3 và 4.

1 4 2 2

5 4 3 3

2 3 1 2