SMARTATM - Máy rút tiền thông minh

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
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


Comments

Please read the guidelines before commenting.



  • -2
    dungolduck  commented on Feb. 12, 2024, 2:24 a.m.

    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


  • 0
    vudinhlong  commented on Jan. 2, 2024, 10:34 a.m.

    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"); }


    • 4
      mquan1503  commented on Jan. 12, 2024, 2:00 p.m.

      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


      • 2
        vudinhlong  commented on Feb. 1, 2024, 5:36 a.m.

        ok tks bro nheee :>