愚直大学 [yukicoder 1042]

https://yukicoder.me/problems/no/1042

前提知識

• 二分探索

解説

https://yukicoder.me/submissions/475012

N^2 <= P + QNlogNを満たす最大のNを求めよという問題。
★の感じから二分探索すればよさそう。
普通に二分探索する。
テクニックとして小数の比較にはEPSを使うのが定石。
今回はA≦Bを判定するが、小数の場合はA≦B+EPSで比較をしよう。

自分は[1,1e9]でEPS=1e-10をするとWAになった。
うーんと思って、適当に[1,1e12],EPS=1e-7にしたら通った。
こういう適当なことをしているからレートが上がらないんだな。

int P, Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> P >> Q;
    double ok = 1, ng = 1e12;
    rep(i, 0, 1010) {
        double md = (ok + ng) / 2;

        if (md * md <= P + 1.0 * Q * md * log2(md) + EPS) ok = md;
        else ng = md;
    }
    printf("%.10f\n", ok);
}