Problem L
Tightly Packed
Consider packing widgets for shipping where widgets cannot be stacked upon each other (2D packing). Each widget has a $1\times ~ l$ footprint and is $1$ unit high.
Boxes are available in any $W$ by $H$ by $1$ size such that $H/2 \leq W \leq 2H$, with $W$ and $H$ being integers. The company wants to minimize the amount of packing material that will be needed to fill empty squares in a box.
Given $N$, the number of widgets to be shipped, what is the smallest number of squares that will be left empty when those widgets are packed for shipping?
Input
Input consists of one line containing an integer $N$, the number of widgets to be packed, where $1 \leq N \leq 10^{16}$.
Output
Print a single line containing an integer denoting the minimum number of empty squares.
| Sample Input 1 | Sample Output 1 |
|---|---|
47 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
523 |
2 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10000000000001 |
6 |
