長さ \(n+1\) の丸太を買って、短い方から丸太を作れるだけ作った後、残りの丸太を買うのが最適です。

この「作れるだけ作った」ときにいくつの丸太が作れるかを求めるためには、\(1 + \dots + k \leq n+1\) を満たす最大の整数 \(k\) を求めれば良いです。これは、\(1 + \dots + k = k(1+k)/2\) であることを使って、二分探索をすることで求めることが可能です。

\(k(1+k)/2 \leq n+1\) から直接答えを計算することも可能かもしれませんが、計算のときに誤差が生じないように気をつける必要があります。

C++による実装