読者です 読者をやめる 読者になる 読者になる

SRM 639 Div2 Medium AliceGameEasy

問題

SRM 639 - TopCoder Wiki

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;
    }
};