問題
A君とB君がそれぞれのターンでゲームをする,iターン目で勝った方はiポイントを得る. 今A君がxポイント,B君がyポイントを得た時,A君が勝った最小ターンを答える問題.
解答
- 何回ターンが出来たかが分かれば,半分問題は解けている.
- ゲームは次を満たすnターン行われた.(x + y) = n * (n+1) / 2
- 最小ターンなので,大きいポイントからA君のポイントに加算し,勝った数を計算する.
class AliceGameEasy { public: long long findMinimumValue(long long x, long long y) { long long n; for (n=0;;n++) if (n*(n+1)>=2*(x+y)) break; long long sum = n*(n+1) / 2; if (x == 0 && y == 0)return 0; if ( sum != (x+y)) return -1; long long res = 0; for (long long t = n; t > 0; t--) { if (x >= t) { x -= t; res++; } } return res; } };