CodeForces Beta Round #15 C. Industrial Nim

Codeforces

C. Industrial Nim

それぞれのダンプの石の数の排他的論理和を計算し、0ならば後手が勝ち、0以外の場合は先手が勝つという定理がある。例えば問題文の最初の例はトラックの石の数が2, 3, 4で2^3^4=5≠0なので先手の勝ち。
今回はトラックの数が非常に多くなりうるので１つずつ計算するとダメ。小さな値で試してみると、xor(k)=1^2^3^……^kは、

  • k　　k%4=0のとき
  • 1　　k%4=1のとき
  • k+1　　k%4=2のとき
  • 0　k%4=3のとき

となることがわかる。i^(i+1)^……^(j-1)^jはxor(j)^xor(i-1)で計算できる。

Nim - Wikipedia, the free encyclopedia

def xor(n):
    return [n,1,n+1,0][n%4]

n = input()
c = 0
for i in range(n):
    x,m = [int(t) for t in raw_input().split()]
    c ^= xor(x+m-1)
    c ^= xor(x-1)

print "bolik" if c==0 else "tolik"