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"); }