| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT137J - Bài J - MUA HÀNG BẰNG TIỀN XU |
Một người đến cửa hàng tạp hóa để mua hàng. Để cho nhanh, anh ta cần chuẩn bị sẵn trong tay một số tiền xu để trao đổi. Vấn đề là anh ta không biết mình sẽ mua những gì nhưng biết số tiền tối đa của tất cả các món hàng cần mua.
Cho trước số tiền xu mỗi loại mà anh ta có và số tiền tối đa cần chi trả C. Hãy xác định số lượng đồng xu các loại ít nhất anh ta cần cầm trên tay để đảm bảo chi trả chính xác được bất cứ số tiền nào trong khoảng từ 1 đến C.
Input
- Có nhiều bộ test. Mỗi bộ test gồm:
- Một dòng ghi hai số C và (1<=C<=109) (1<=m<=1000) trong đó C là số tiền tối đa cần trả, m là số loại đồng xu mà anh ta mang theo.
- m dòng tiếp theo, mỗi dòng ghi hai số v và n (1 <= v, n <= 1000) theo thứ tự là giá trị của mỗi loại đồng xu và số lượng hiện có.
- Đầu vào kết thúc với một dòng ghi duy nhất một số 0.
Output
- Với mỗi bộ test, in ra màn hình trên một dòng số đồng xu các loại mà anh ta cần cầm trên tay. Nếu không thể xác định được thì ghi “Not possible”
Example
Input:
4 2
2 1
1 3
9 3
1 5
8 2
7 1
0 Output:
3
Not possible
| Được gửi lên bởi: | adm |
| Ngày: | 2013-03-25 |
| Thời gian chạy: | 5s |
| 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 |
