4mm Tomato

2 secs 1024 MB

take44444

問題

提出

テストケース

解説

$[N]$ のgrundy数を求めることを考えます．

$[2]$ ～ $[2M-1]$ のgrundy数は $0$ です． $[2M]$ 以降のgrundy数は以下で求めることができます．

$g_{[n]} = \mathrm{mex}(\{i+j = n \ になるような\ i,j\ における [i] \oplus [j]\})$

$n$ の小さい方から順にこれを求めて行くことで， $[N]$ のgrundy数を $\mathrm{O}(N^2)$ で求めることができます．

参考コードは以下です．

xxxxxxxxxx
 
def mex(l):
  ret = 0
  for e in sorted(l):
    ret += ret == e
  return ret
​
n, m = map(int, input().split())
grundy = [0]*(2*m)
​
for i in range(2*m, n+1):
  sprague = []
  for l in range(m, i):
    r = i - l
    if l > r: break
    sprague.append(grundy[l]^grundy[r])
  grundy.append(mex(sprague))
​
print("Bob" if grundy[n] == 0 else "Alice")