| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT125K - Tổng số tiền xu ít nhất |
Mr. A đi chợ mua hàng. Anh ta mang theo một số đồng xu các loại (giả sử trong hệ thống tiền tệ tại khu nhà Mr.A chỉ dùng các loại tiền xu). Cho trước giá của mặt hàng cần mua, hãy tính giúp Mr.A xem ít nhất sẽ có bao nhiêu đồng xu cần trao đổi (cộng cả số xu trả cho người bán hàng và số xu nhận lại tiền thừa).
Giả sử sản phẩm cần mua có giá là T (1 ≤ T ≤ 10,000). Hệ thống tiền tệ có N loại xu khác nhau (1 ≤ N ≤ 100), với giá trị V1, V2, ..., VN (1 ≤ Vi ≤ 120). Mr.A có C1 xu loại V1, C2 xu loại V2, ...., và CN xu loại VN (0 ≤ Ci ≤ 10,000). Người bán hàng có số lượng không giới hạn của mỗi loại tiền xu nhưng sẽ luôn trả lại bằng ít xu nhất có thể.
Input
Dòng 1: Hai số nguyên N và T.
Dòng 2: N số nguyên mô tả các mệnh giá tiền xu (V1, V2, ..., VN )
Dòng 3: N số nguyên mô tả số tiền xu mỗi loại mà Mr.A có (C1, C2, ..., CN)
Output
Dòng 1: Ghi giá trị số lượng đồng xu ít nhất cần trao đổi. Nếu không thể mua được hàng, in ra -1.
Example
Input: 3 70
5 25 50
5 2 1
Output: 3
| Được gửi lên bởi: | adm |
| Ngày: | 2012-03-14 |
| 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 |
