問題一覧 > 通常問題

No.1106 🦉 何事もバランスが大事

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 44
作問者 : yuppe19 😺yuppe19 😺 / テスター : hotmanwwhotmanww
9 ProblemId : 2573 / 出題時の順位表
問題文最終更新日: 2020-06-06 09:40:41

問題文

重さ $1, 2, \cdots, N$ の荷物が各ひとつずつ、全部で $N$ 個あります。
これらの荷物のそれぞれを、分銅を使って天秤で釣り合わせます。

分銅は $5^{k}$($k$ は $0$ 以上の整数)の重さのものが $2$ 個ずつしかありません。
つまり、分銅の重さは軽いものから $1, 1, 5, 5, 25, 25, 125, 125, \cdots$ です。上限はありません。

分銅は天秤の左右どちらにも置くことができます。
天秤で釣り合わせた後は毎回荷物も分銅も天秤から下ろすので、一度使った分銅も再び使えます。

何事もバランスが大事だと思っているあなたは、天秤で釣り合わせたときに分銅の個数も左右で一致してほしいです。
そのような分銅の置き方ができる荷物はいくつあるか数えてください。

入力

$N$

$N$ は $1 \le N \le 10^{18}$ を満たす整数です。

出力

$N$ 個の荷物のうち、天秤で釣り合わせたときに分銅の個数が左右で一致するような荷物の個数を出力し、改行してください。

サンプル

サンプル1
入力
4
出力
1
状況を表にすると、このようになります。

したがって、重さ $1$ 以上 $4$ 以下の荷物のうち、分銅の個数が一致するのは重さ $4$ のひとつのみなので、$1$ を出力します。
サンプル2
入力
9
出力
2
荷物の重さが $4$ と $8$ のときに左右の分銅の個数が一致します。
荷物の重さが $8$ のとき、分銅は荷物側に重さ $1$ をふたつ、反対側に重さ $5$ をふたつ置くことになります。
サンプル3
入力
25
出力
5
荷物の重さが $4, 8, 16, 20, 24$ のときに左右の分銅の個数が一致します。
荷物の重さが $16$ のとき、分銅は荷物側に重さ $5$ をふたつ、反対側に重さ $1$ と $25$ をひとつずつ置くことになります。
荷物の重さが $20$ のとき、分銅は荷物側に重さ $5$ をひとつ、反対側に重さ $25$ をひとつ置くことになります。
荷物の重さが $24$ のとき、分銅は荷物側に重さ $1$ をひとつ、反対側に重さ $25$ をひとつ置くことになります。
サンプル4
入力
3364
出力
433
サンプル5
入力
1000000000000000000
出力
55085687930311653

入力値が最大のケースです。

---

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。