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

SRM 635 Div2 Medium QuadraticLaw

問題

SRM 635 - TopCoder Wiki

教師が授業にx分遅れるとx2分予定より早く講義を終えなければならない. 沢山遅れると,ついた瞬間に授業が終わるという場合も考えられる. 授業時間dが与えられた時,授業をすることができる,最大の遅刻時間を求める問題.

解答

  • 授業可能から,授業不可能になる境目が必ず存在する.
  • 二分探索で求めることが出来る.
  • 入力が大きいので,オーバーフローを起こさないように気をつける.(System Testで半分以上落ちているのはおそらくこのせい)
class QuadraticLaw
{
public:
  long long getTime(long long d)
    {
      long long high = ((long long)sqrt(d)) + 1;
      long long low = 0;
      long long mid = (low + high) / 2;
      while (low <= high) {
        mid = (low + high) / 2;
        // cout << "low=" << low << " high=" << high << " mid=" << mid << endl;
        if ((d - mid - mid * mid) >= 0) {
          low = mid + 1;
        }else {
          high = mid - 1;
        }
      }
      // return mid;
      return (low + high) / 2;
    }
};