No.634 硬貨の枚数1
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 168
作問者 :
しらっ亭
/ テスター :
はむこ
タグ : / 解いたユーザー数 168
作問者 :
しらっ亭
/ テスター :
はむこ
問題文最終更新日: 2018-01-21 13:45:20
問題文
YUKI国の通貨の単位は円と呼ばれ、額面が三角数であるような硬貨が流通しています。
すなわち、任意の正整数 $k$ に対して、$k \times (k+1) \div 2$ 円の硬貨が流通しています。
流通している硬貨を額面を小さい方からいくつか列挙すると、$1, 3, 6, 10, 15, 21, 28, \dots $ 円です。
雪男くんは、全ての額面の硬貨を $10^{100}$ 枚持っており、$N$ 円の品物を購入しようと思っています。
その際、YUKI国の硬貨でちょうど $N$ 円となるように支払いを行います。
雪男くんは、支払いに使用する硬貨の枚数を最小化したいです。
支払いに使用する硬貨の枚数の最小値を求めてください。
入力
N
$1 \le N \le 10^{7}$
$N$ は整数
出力
答えを1行で出力してください。最後に改行してください。
サンプル
サンプル1
入力
8
出力
3
例えば、$8$ 円を支払うのに、$6$ 円の硬貨を $1$ 枚、$1$ 円の硬貨を $2$ 枚使用します。使用する硬貨の枚数は $3$ 枚となり、これが最小です。
サンプル2
入力
10
出力
1
額面 $10$ 円の硬貨 $1$ 枚の支払いが最小です。
サンプル3
入力
15415
出力
2
額面 $15$ 円と $15400$ 円の硬貨を $1$ 枚ずつの、計2枚で支払うことが可能です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。