TheAlgorithms-Python
65 строк · 1.4 Кб
1"""
2Coin sums
3Problem 31: https://projecteuler.net/problem=31
4
5In England the currency is made up of pound, £, and pence, p, and there are
6eight coins in general circulation:
7
81p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
9It is possible to make £2 in the following way:
10
111×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
12How many different ways can £2 be made using any number of coins?
13"""
14
15
16def one_pence() -> int:
17return 1
18
19
20def two_pence(x: int) -> int:
21return 0 if x < 0 else two_pence(x - 2) + one_pence()
22
23
24def five_pence(x: int) -> int:
25return 0 if x < 0 else five_pence(x - 5) + two_pence(x)
26
27
28def ten_pence(x: int) -> int:
29return 0 if x < 0 else ten_pence(x - 10) + five_pence(x)
30
31
32def twenty_pence(x: int) -> int:
33return 0 if x < 0 else twenty_pence(x - 20) + ten_pence(x)
34
35
36def fifty_pence(x: int) -> int:
37return 0 if x < 0 else fifty_pence(x - 50) + twenty_pence(x)
38
39
40def one_pound(x: int) -> int:
41return 0 if x < 0 else one_pound(x - 100) + fifty_pence(x)
42
43
44def two_pound(x: int) -> int:
45return 0 if x < 0 else two_pound(x - 200) + one_pound(x)
46
47
48def solution(n: int = 200) -> int:
49"""Returns the number of different ways can n pence be made using any number of
50coins?
51
52>>> solution(500)
536295434
54>>> solution(200)
5573682
56>>> solution(50)
57451
58>>> solution(10)
5911
60"""
61return two_pound(n)
62
63
64if __name__ == "__main__":
65print(solution(int(input().strip())))
66