SHARE
TWEET

Untitled

a guest Oct 21st, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. a = [50, 100, 200, 500, 1000, 2000, 5000]
  2. s = int(input())
  3. inf = 10 ** 6
  4. prev = [-1] * (s + 1)
  5. f = [0]  + [inf] * s
  6. for i in range(1, s + 1):
  7.     for j in range(len(a)):
  8.         if i - a[j] >= 0 and f[i - a[j]] < f[i]:
  9.             f[i] = f[i - a[j]]
  10.             prev[i] = a[j]
  11.     f[i] += 1
  12. print(f[s])
  13. ans = []
  14. curr = s
  15. while curr > 0:
  16.     ans.append(prev[curr])
  17.     curr -= prev[curr]
  18. print(ans)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top