Yuki 361 門松ゲーム2 ( SG, Game Theory )

No.361 門松ゲーム2 - yukicoder

題意：
一開始有一個長度 L 單位的棒子。輪流操作，操作要選擇一個棒子，砍成三個不同長度的棒子，令這三個棒子的長度為 L1, L2, L3，則必須滿足：
max( L1, L2, L3 ) - min( L1, L2, L3 ) ≤ D
先不能操作的人輸，問誰贏。

制約：
L, D ≤ 500

解法：
暴力 SG。

時間 / 空間複雜度：
O( L^3 )

L, D = map( int, input().split() )

sg = [ 0 for i in range( L + 1 ) ]
for i in range( L + 1 ):
  bag = set()
  for j in range( 1, i ):
    for k in range( j + 1, i - j ):
      l = i - j - k
      if not ( j < k < l ): continue
      if not ( l - j <= D ): continue
      bag.add( sg[ j ] ^ sg[ k ] ^ sg[ l ] )
  for j in range( 1000000 ):
    if j not in bag:
      sg[ i ] = j
      break

print( [ "matsu", "kado" ][ sg[ L ] > 0 ] )