TopCoder SRM 639 Div1 Easy AliceGame
問題:
何回かAliceとKirtoでゲームをする、それぞれの回ではAliceのKirtoの勝った方が1,3,5,7,... 2i-1点となる。負けた方は0点。
最終的にAliceはx点、Kirtoはy点になる。
Aliceの勝利回数は最小で何回か。存在しなければ-1を返す
0<= x,y <= 1,000,000,000,000
回答:
1+3+5+...+(2n-1) = n^2 なので、x+yからnを求める。整数nが存在しなければ-1を返す。
xについて、i=n..1をとし、x>=i*2-1ならxから引いていく。
ただし、残りが"2"になってしまうと、その後消去することができないので、"2"にはならないようにする。例えば9が残っている場合、9-7=2とするとダメだけど、7を飛ばして9-5-3-1=0で0にすることができる。
コード:
https://paiza.io/projects/eiZmkvH3lqANJttOilEtqQ
感想:
残りが2の場合を無視することに気付けなかった。。。
ほとんどの人が気付けなかったようで、ほとんどの人が撃墜されてひどい結果に。。。