SRM 615 Div2 Medium LongLongTripDiv2

問題

SRM 615 - TopCoder Wiki

距離1もしくは距離Bにジャンプできる時, 1方向のみT回ジャンプして距離Dに到達できるかどうか判定する問題.

解答

距離Bのジャンプの回数によって到達できる距離は単調増加に伸びる. そのため,距離Bのジャンプの回数を二分探索で求めることが出来る.

解説を見ると,exactにO(1)で求めることが出来た. うーん,なるほど.

class LongLongTripDiv2
{
public:
  string isAble(long long D, int T, int B)
    {
      long long low = 0;
      long long up = T;
      while (low <= up) {
        long long mid = (low + up) / 2;
        long long v = mid * B + (T - mid);
        if (v == D) return "Possible";
        else if (v < D) {
          low = mid + 1;
        }else {
          up = mid - 1;
        }
      }
      return "Impossible";
    }
};