cafelier@SRM

SRM526.5 250

あとで | 13:56 |

• 同じ部屋のxiaowuc1さんの解がかっこよかった

class MagicCandy { public:
   int whichOne(int n)
   {
      // r が最後まで生き残るかどうか…？
      int r = n;
      while( n > 1 ) {
         const int sn = int(sqrt(n));
         // sn*sn == n だったら平方数になってるので死んでる
         // r-1 は生きてるはずなので引き続きそれの生き残りチェック
         r -= (sn*sn == n);
         n -= sn;
      }
      return r;
   }
};

• n = k*k+1 の形だったら２歩で k*k+1-k = (k-1)*(k-1)+k → (k-1)*(k-1)+1
• と進むので、一度平方数+1になったら最後まで死なないので、rがそこまで生きてたらr-1も生きてる
• ほげー