Морской бой

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

요약

1 x n 크기 판에서 길이 k인 배 1척, 길이 k-1인 배 2척, ..., 길이 1인 배 k척을 서로 닿지 않게 놓을 수 있는 최대 k를 구한다.

난이도: 보통10점 중 6점
유형: 수학, 이분 탐색, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

Однажды Рик, исследуя измерение E5, придумал идею прибора, который изменит человечество. Обитатели измерения Е5 раз в тысячелетие устраивают большой турнир по одномерному морскому бою. Прибор будет выполнять следующую задачу: помогать участнику турнира по одномерному морскому бою расставить максимальное количество кораблей на поле. Он еще не решил, как именно собирается менять человечество с помощью своего изобретения, но уверен, что сможет, как минимум, внедрить игру в одномерный морской бой в наше с вами измерение и разнообразить жизнь людей.

Поле в игре в одномерный морской бой имеет размеры $1 \times n$ . Задача прибора --- найти такое максимальное $k$ , что на поле можно расставить один корабль размера $1 \times k$ , два корабля размера $1 \times (k - 1)$ , $\ldots$ , $k$ кораблей размера $1 \times 1$ , причем корабли, как и в обычном морском бое, не должны касаться друг друга и пересекаться.

입력

В единственной строке входных данных дано число $n$ --- количество клеток поля ( $0 \le n \le 10^{18}$ ).

출력

Выведите единственное число --- такое максимальное $k$ , что можно расставить корабли, как описано в условии.

힌트

Пояснение к примеру: для поля $1 \times 7$ ответ равен 2. Расставить один корабль размера $1 \times 2$ и два корабля размера $1 \times 1$ можно следующим образом:

예제1

예제 1
입력
```
7
```
예상 출력
```
2
```