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