The optimal strategy is to buy the log of length \(n+1\), cut it to make as many shortest logs as possible, and buy the rest of the logs.

To find how many shortest logs can be made, we need to find the maximum integer \(k\) such that \(1 + \dots + k \leq n+1\). We can find it with binary search using \(1 + \dots + k = k(1+k)/2\).

It may be possible to directly compute the answer from \(k(1+k)/2 \leq n+1\), but watch out for errors in computing.

Sample Implementation in C++