はまやんはまやんはまやん

hamayanhamayan's blog

 お や す み  [yukicoder No.648]

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

前提知識

解法

https://yukicoder.me/submissions/235200

二分探索で解いていく。
「f(x) := x秒目までに柵を越えた羊の数」
これは「f(x) = x * (x + 1) / 2」となる。
あとは、[1,2*10^9]の範囲で越えた数がN以上となる境目を探す。
境目が丁度NならばYES、そうでないならぴったりは無理なのでNO

ll N;
//---------------------------------------------------------------------------------------------------
ll f(ll x) { return x * (x + 1) / 2; }
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    ll ng = 0, ok = 2000000000LL;
    while (ng + 1 != ok) {
        ll x = (ng + ok) / 2;
        if (N <= f(x)) ok = x;
        else ng = x;
    }

    if (f(ok) == N) printf("YES\n%lld\n", ok);
    else printf("NO\n");
}