Link Sub: http://www.spoj.com/PTIT/problems/PTIT125B/
Người Gửi: Funny
- Problem:
FJ muốn mua quà cho N (1<=N<=1000) con bò của mình bằng cách sử dụng tổng số tiền là B (1<=B<=1,000,000,000). Bò i yêu cầu món quà có giá trị P(i) và có phí vận chuyển S(i) (nên tổng số tiền phải trả là P(i)+S(i) nếu FJ mua món quà đó). FJ có 1 phiếu giảm giá đặc biệt giúp anh có thể mua một món quà với giá bằng một nửa giá trị của món quà đó. Nếu FJ sử dụng phiếu giảm giá cho bò i, anh ấy cần phải thanh toán tổng số tiền là P(i)/2+S(i).
Để cho dễ dàng, tất cả các P(i) đều là số chẵn. Bạn hãy giúp FJ xác định xem ông có thể mua quà cho tối đa là bao nhiêu con bò.
Input
- Dòng 1: 2 số nguyên N và B
- Dòng 2..1+N: Dòng i+1 chứa 2 số nguyên P(i) và S(i) (0<=P(i),S(i)<=1,000,000,000)
Output
Một số nguyên duy nhất là số bò tối đa mà FJ có thể mua quà
Example:
Một số nguyên duy nhất là số bò tối đa mà FJ có thể mua quà
Input
5 24
4 2
2 0
8 1
6 3
12 5
Output:
4
- Solution:
Giải thích: FJ có thể mua quà cho các con bò từ 1 đến 4, bằng cách sử dụng phiếu giảm giá cho bò 3. Tổng số tiền thanh toán là (4+2)+(2+0)+(4+1)+(6+3) = 22- Ghi dữ liệu và đồng thời tính luôn độ giảm giá nếu áp dụng phiếu giảm.
- Sắp xếp tăng dần giá các món hàng.
- Mua lần lượt từ bé đến lớn, nếu còn mua được món hàng nào thì mua món hàng đó và cập nhật lại tiền.
- Nếu đạt ngưỡng không mua tiếp được thì tìm con có độ giảm giá lớn nhất (trả lại hàng và lấy thêm tiền :v). Dùng tiền đã tăng thêm lại tiếp tục mua cho đến khi đạt ngưỡng không mua được. =))