| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT125B - Mua quà |
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
Input: 5 24
4 2
2 0
8 1
6 3
12 5
Output: 4
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
| Được gửi lên bởi: | adm |
| Ngày: | 2012-03-12 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2017-07-26 17:56:42
PTIT125B: https://e16cn-ptit.blogspot.com/2017/12/ptit125b-mua-qua.html Last edit: 2017-12-13 22:19:42 |
|
|
2016-06-02 05:41:48
tu3297 Last edit: 2016-06-02 05:42:07 |
|
|
2013-05-18 10:48:29 an IM3 Ex-Member of Bit
bài này không hiểu sao làm NLogN 0.02s lại chậm hơn N^2 0.01s =))) |
