No.634 Number of Coins 1
しらっ亭
はむこProblem Statement
The currency unit of the YUKI Kingdom is called the yen, and coins whose denominations are triangular numbers are in circulation.
That is, for every positive integer $k$, a coin of $k \times (k+1) \div 2$ yen is in circulation.
Listing some of the coins in circulation in ascending order of denomination, they are $1, 3, 6, 10, 15, 21, 28, \dots $ yen.
Yukio has $10^{100}$ coins of every denomination and wants to buy an item that costs $N$ yen.
He will pay with coins of the YUKI Kingdom so that the total is exactly $N$ yen.
Yukio wants to minimize the number of coins used for the payment.
Find the minimum number of coins used for the payment.
Input
N
$1 \le N \le 10^{7}$
$N$ is an integer.
Output
Output the answer in 1 line. Print a newline at the end.
Sample
Sample 1
Input
8
Output
3
For example, to pay $8$ yen, use $1$ coin of $6$ yen and $2$ coins of $1$ yen. The number of coins used is $3$, and this is the minimum.
Sample 2
Input
10
Output
1
Paying with a single coin ($1$ coin) of denomination $10$ yen is the minimum.
Sample 3
Input
15415
Output
2
It is possible to pay with $1$ coin each of denominations $15$ yen and $15400$ yen, for a total of 2 coins.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。