forked from y-tetsu/math_puzzle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
q30.py
43 lines (34 loc) · 1.12 KB
/
q30.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Q30
"""
N = 20
MEMO = {"1": 1}
def set_tap(remain):
"""
テーブルタップをつなぐ
"""
if str(remain) in MEMO:
return MEMO[str(remain)]
cnt = 0
for i in range(1, int(remain / 2) + 1):
if remain - i == i:
cnt += set_tap(i) * (set_tap(i) + 1) / 2
else:
cnt += set_tap(remain - i) * set_tap(i)
for i in range(1, int(remain / 3) + 1):
for j in range(i, int((remain - i) / 2) + 1):
if remain - (i + j) == i and i == j:
cnt += set_tap(i) * (set_tap(i) + 1) * (set_tap(i) + 2) / 6
elif remain - (i - j) == i:
cnt += set_tap(i) * (set_tap(i) + 1) * set_tap(j) / 2
elif i == j:
cnt += set_tap(remain - (i + j)) * set_tap(i) * (set_tap(i) + 1) / 2
elif remain - (i + j) == j:
cnt += set_tap(j) * (set_tap(j) + 1) * set_tap(i) / 2
else:
cnt += set_tap(remain - (i + j)) * set_tap(j) * set_tap(i)
MEMO[str(remain)] = int(cnt)
return int(cnt)
print(set_tap(N))