SMARTATM - Máy rút tiền thông minh
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Ở cổng trường THPT Chuyên Sơn La mới được lắp mới một máy rút tiền tự động. Trong máy có ~n~ loại tiền mệnh giá lần lượt là ~a_1, a_2, …, a_n~, mỗi mệnh giá có số lượng đủ nhiều.
Khi khách hàng có yêu cầu rút số tiền ~M~, chương trình điều khiển sẽ xác định xem có thể trả được số tiền đúng bằng ~M~ không, nếu có, chương trình điều khiển sẽ chọn cách trả với số lượng tờ ít nhất.
Yêu cầu: Hãy tính số lượng tờ tiền ít nhất để trả số tiền ~M~.
Input
- Dòng đầu chứa hai số nguyên dương ~n~ và ~M~;
- Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, …, a_n~ được sắp xếp theo thứ tự tăng dần.
Giới hạn:
- ~1 ≤ n ≤ 20; 1 ≤ a_i ≤ 10^4; 1 ≤ M ≤ 10^5~
Output
- Ghi ra một dòng duy nhất chứa số nguyên dương là số lượng tờ tiền ít nhất nếu có phương án trả, ngược lại ghi ra ~-1~.
Sample
Input #1
3 130
10 60 100
Output #1
3
Hint
Xét #1:Trả hai tờ ~60~ và một tờ ~10~
Problem source: Chuyên Sơn La Online Judge
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
bài này phải dùng qhd nhá ae link tham khảo: https://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/?ref=lbp
Test 6 trở đi là điều kiện gì vậy ạ :))
include<stdio.h>
int main(){ int n, m; scanf("%d %d", &n, &m); int a[n+1]; for(int i=0; i<n; i++){ scanf("%d", &a[i]); } int res=1e9, dk=0; for(int i=n-1; i>=0; i--){ int dem=0, tmp=m; for(int j=i; j>=0; j--){ dem += tmp/a[j]; tmp %= a[j]; }if(tmp==0){ dk = 1; if(dem < res) res = dem; } }if(dk==1) printf("%d", res); else printf("-1"); }
nó vẫn như bth thôi man, man làm sai rồi, không thể cứ lấy tờ tiền rồi thêm tờ nhỏ hơn được , ví dụ cần 220 từ 10 60 100, thì code của bạn sẽ là 2 tờ 100 và 2 tờ 10, nhưng đáp án của nó là 2 tờ 60 1 tờ 100
ok tks bro nheee :>