SRM 639 Div1 Easy, AliceGame
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13490&rd=16082
Alice, Kirito 2人がゲームをする. ゲームはターン1から始まり有限ターンからなる. 各ターンでそれぞれ勝者が決まり, i ターン目で勝利すると2*i-1ポイントもらえる. long long int x, y が与えられる. ゲーム終了時に Alice が x ポイント, Kirito が y ポイントとなるようなパターンは存在するか. 存在するならば Alice が勝利する必要がある最小ターン数を出力せよ. 存在しないならば -1 を出力せよ.
0 <= x, y <= 1012
方針
ターン数 T は √(x+y) で得られる.
計 i ターンの勝利で x ポイント稼げる必要十分条件:
- x が 1 以上 2*T-1 以下の相異なる i 個の奇数の和で表せる
- ⇔ (x+i)/2 が 1 以上 T 以下の相異なる i 個の整数の和で表せる
この条件を満たすかどうかを i = 1 .. T で確かめれば良い.
解答
class AliceGame { public: long long findMinimumValue(long long x, long long y) { ll turns = sqrt(x+y)+0.01; if (turns*turns != x+y) return -1; for (ll i = 0; i <= turns; i++) { ll min = i*(i+1)/2, max = (2*turns-i+1)*i/2; if ((x+i) % 2 == 0 && (x+i)/2 >= min && (x+i)/2 <= max) return i; } return -1; } };
雑感
大きい奇数から順に足していく方法だと, 2 が残る場合のコーナーケースがあり, ここで大勢落ちていたっぽい. 2 が残る場合だけ除外するとそれでも通るが, 証明がわからない.