ARC 072 D - Alice&Brown ( Game Theory, SG )
D: Alice&Brown - AtCoder Regular Contest 072 | AtCoder
題意:
兩堆石頭,數量 X, Y。輪流操作,一次選一個正整數的偶數 v,從一個至少有 v 個石頭的堆裡除去,並在另一堆上添加 v / 2 顆石頭。先不能操作的人輸。問雙方最佳操作下誰贏。
制約:
0 ≤ X, Y ≤ 1e18
解法:
用 SG Value 暴力建表肉眼觀察,可以發現 Line 26 ~ 29 的規則。
時間 / 空間複雜度:
O( 1 )
'''dp = [ [ -1 for i in range( 200 ) ] for j in range( 200 ) ] def dfs( x, y ): global dp if dp[ x ][ y ] != -1: return dp[ x ][ y ] if x <= 1 and y <= 1: dp[ x ][ y ] = 0 return dp[ x ][ y ] bag = set() for i in range( 2, x + 1, 2 ): bag.add( dfs( x - i, y + i // 2 ) ) for i in range( 2, y + 1, 2 ): bag.add( dfs( x + i // 2, y - i ) ) for i in range( 1000000 ): if not ( i in bag ): dp[ x ][ y ] = i return dp[ x ][ y ] for i in range( 0, 100 ): for j in range( i, 100 ): if dfs( i, j ) == 0: print( i, j )''' X, Y = map( int, input().split() ) if X > Y: X, Y = Y, X if X == Y or X + 1 == Y: print( "Brown" ) else: print( "Alice" )