Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- nominals = [1, 10, 100, 500]
- s = int(input("Введите сумму: "))
- INF = 10**6
- a = [INF]*(s+1)
- from_ = [-1] * (s+1)
- for i in nominals:
- if i <= s:
- a[i] = 1
- from_[i] = 0
- for i in range(1, s+1):
- for stepback in nominals:
- if (i <= stepback):
- continue
- previous = a[i-stepback] + 1
- if a[i] > previous:
- from_[i] = i - stepback
- a[i] = previous
- print("Купюр и монет: ", a[s])
- # Восстанавливаем ответ
- to = s
- answer = [0]*4
- while from_[to] != -1:
- stepback = to - from_[to]
- if stepback == 1:
- answer[0] += 1
- if stepback == 10:
- answer[1] += 1
- if stepback == 100:
- answer[2] += 1
- if stepback == 500:
- answer[3] += 1
- to = from_[to]
- print("1:", answer[0])
- print("10:", answer[1])
- print("100:", answer[2])
- print("500:", answer[3])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement