blob: 54902add8cfafbaffe1533d3b8b40711707f6384 (
plain) (
blame)
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
|
hashStuff = {0: 0, 1: 1, 2: 1, 3: 1, 4: 2, 5: 2}
def MEX(S: set) -> int:
i = 0
while True:
if i not in S:
return i
i += 1
def P(n: int) -> int:
"""
Compute nimber for a path of a certain length
"""
if n in hashStuff:
return hashStuff[n]
res = Prec(n)
hashStuff[n] = res
return res
def Prec(n: int) -> int:
S = set()
# Works only for n >= 5
S.add(P(n-2))
S.add(P(n-3))
S.add(P(n-4))
for i in range(2, n-5+1):
S.add(nimAdd(P(i), P(n-3-i)))
return MEX(S)
def nimAdd(x: int, y: int) -> int:
return x ^ y
|
