PKU復活したっぽい

なんとなくやってみた。中国語だけど。
1067's Status List
Excite翻訳（とフィーリング）によると、問題の内容は二人ゲーム。二つの石の山があって、二人は交互に山から石を取っていき、最後の石を取った方が勝ちとなる。ただし石の取り方は、(1)片方の山から好きな数だけ取る、(2)両方の山から同じ数ずつ取る、の二つ（パスはなし）。それぞれの山の石の数が入力で与えられたとき(1,000,000,000以下)、両者が最善を尽くすという仮定の下、先手が勝ちなら1を、負けなら0を出力する。
コード長では1位だけど、（色々と）微妙。
ひどいのだけど、ソース（と雑多）を晒しておく。
GCCで123バイト。

a,b;
main(n){
  double p=sqrt(5)/2+.5;
  for(;~scanf("%d%d",&a,&b);printf("%d\n",a||n-b))
    a>b?n=b,b=a,a=n:0,n=a/p+1,a-=n*p,n*=p*p;
}

p=黄金比とおき、数列a_n=floor(n*p), b_n=floor(n*p*p)を考え、入力(a,b)があるnについて(a_n, b_n)の組に入っているかどうか調べて、入っていれば先手の負けとしています。
微妙なのは総合で1位を取れなかったことではなく（それはそれで悲しいのですが）、どうしてこれで解けているのか理解できてないから。先手が負ける石の数の組を列挙してみると確かに黄金比くらいにはなっていることは判ったのだけど、証明をさぼってぐぐってしまった（Wythoff's Game -- from Wolfram MathWorld）。
まぁ今回はコードを短くしてみたかっただけ（たまたまPKUが落ちてたからだけど）だったりするのですが、短いコードってパズルのようで面白いですね。とくに最初に書いたコードから括弧が必要最小限以外消せたのは面白かったです。
a<=bとなるように入れ替えをやっている部分と黄金比の部分が冗長な気がするんだけど、これ以上は思いつきませんでした。