まででなく，
と
が入っているのが気になる．
まず，丸太の買い方として，同じ値段なら長いほうが得． 言い換えると，短いほうで出来るなら，長いほうでも出来る， いわば上位互換． 上位互換の考えは，貪欲法を示すときによく使う． 大きい方から買うので， を買う．
買い方の次に考えるのは切り方． 買った丸太のうち，切らないでそのまま使えるものは使ったほうが良さそう． 実際，その考えで正しい．
買った丸太のうち短い方から，分割の仕方を決めていく． 長さ の丸太をもし切るのなら，もっと大きい丸太の中から， 長さ
のパーツを切らないといけない． その2つを取り換えれば，長さ
の丸太を切らずに済む． これを繰り返せば，
以外の丸太は切らなくて済む．
ここまでくれば，買う本数 を固定したときに， それで条件を満たすか(
を作れるか)は判定できる． つまり，
の丸太から，残った作りたいパーツを切り取れるかを判定すればよい．
また， 沢山丸太を買ったほうが上位互換なので， に関して単調なことも言えるため， binary search で解ける．
の計算をするときに，最悪
程度かかる． n が
程度なので，long long だと桁あふれするので， boost の可変長整数を用いる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
namespace mp = boost::multiprecision;
using ll = mp::cpp_int;
int main() {
ll n;
cin >> n;
auto f = [&](ll x) -> bool {
if(x >= n) return true;
ll k = n+1 - x;
if(k <= 0) return true;
return (k+1)*k <= 2*(n+1);
};
ll ok, ng;
ok = n, ng = 0;
while(abs(ok-ng) > 1){
ll md = (ok + ng)/2;
if(f(md)) ok = md;
else ng = md;
}
cout << ok << endl;
return 0;
}
