Tightly Packed

시간 제한1초메모리 제한1024 MB

요약

한 변이 정수인 W와 H에 대해 H/2 ≤ W ≤ 2H를 만족하는 상자에 1x1 위젯 N개를 넣을 때 남는 빈칸 수의 최솟값을 구한다.

난이도: 보통10점 중 6점
유형: 수학, 정수론, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Consider packing widgets for shipping where widgets cannot be stacked upon each other (2D packing). Each widget has a 1x1 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 consists of one line containing an integer $N$ , the number of widgets to be packed. $1 \leq N \leq 10^{16}$ .

출력

Print a single line containing an integer denoting the minimum number of empty squares.

예제3

예제 1
입력
```
47
```
예상 출력
```
1
```
예제 2
입력
```
523
```
예상 출력
```
2
```
예제 3
입력
```
10000000000001
```
예상 출력
```
6
```