fork download
copy 
  1. #
  2. # We consider N (N<=1000) types of banknotes, of different values,
  3. # of each there being an unlimited number of pieces. Determine a payment
  4. # method of payment, of value S using a minimum numbers of banknotes.
  5. #
  6. # Input:
  7. # N = 5
  8. # S = 100
  9. #         3,15,1,5,2
  10. #
  11. # Output: 6 * 15
  12. #         2 * 5
  13.  
  14. def fn():
  15.     def sorting(sign):
  16.         n = len(B)
  17.         for i in range(1, n):
  18.             j = i - 1
  19.             aux = B[i]
  20.             while j >= 0 and B[j]*sign>aux*sign:
  21.                 B[j+1] = B[j]
  22.                 j-=1
  23.             B[j+1] = aux
  24.  
  25.     def solve():
  26.         global S
  27.         sorting(-1)
  28.         for i in B:
  29.             if S>=i:
  30.                print("%d * %d"%(S//i,i))
  31.             S-=(S//i)*i
  32.             if S == 0:
  33.                 break
  34.         if S>0:
  35.             print("No Solution")
  36.     global S
  37.     N = int(input("N="))
  38.     S = int(input("S="))
  39.     B = [0]*(N)
  40.     for i in range(0, N):
  41.         B[i] = int(input())
  42.     solve()
  43. fn()
  44.  
Success #stdin #stdout 0.04s 9732KB
comments (?)
stdin
copy 
5 
100
3 
15 
1 
5 
2
stdout
copy 
N=S=6 * 15
2 * 5
https://ideone.com/aaSgdm
Payment Method
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!