No.71 そろばん

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 237
作問者 : yuki2006yuki2006
0 ProblemId : 140 / 出題時の順位表

問題文

コンピュータが登場する前、計算する道具といえば「そろばん」だった。
今回は、そのそろばんがテーマの問題である。

一般的なそろばんは、一列だけ見ると、5つ珠があり0〜9まで表すことができる。

これは、1列に串刺し状の上部1つの珠と下部4つの珠に分けて、
下部の動いている珠の数、上部の動いている珠分さらに5を足すという数の表現方法を行う。
つまり上部は、下部の数の繰り上がり数と見ることができる。
参考:Wikipedia
http://ja.wikipedia.org/wiki/%E3%81%9D%E3%82%8D%E3%81%B0%E3%82%93#.E5.B8.83.E6.95.B0.E6.B3.95
(そろばんを知らない方はごめんなさい。。)

このとき、Ursaは特殊なそろばんを思いついた。
一列に使える珠の合計を$N$個とし、上部と下部に使える珠の数は、合計で$N$個であれば自由に決めることができるとする。
この時、一列分で表現できる最大の数を求めてください。

ただし、表現方法としてできるのは、それぞれの珠の上げ下げの状態のみで判断するとする。
中途半端に動かすなどできないとし、上部・下部はそれぞれ連続に並んでいる珠なので3つ目が動くなら、1つ目2つ目も連動して動くような機構であるとする。
また、0から最大の数まで一意的な表現ができるとする。

入力

$N$

入力は整数で与えられる。

  • $1 \le N \le 1000000 =10^6 $

出力

一列分で表現できる最大の数を求めて出力してください。
最後に改行してください。

サンプル

サンプル1
入力
5
出力
11

一般的なそろばんと同じ数だが、下部に3つ珠、上部に2つ珠にすると11まで表現できる。

サンプル2
入力
19
出力
109

うまくすると109まで表現できる。

サンプル3
入力
1000000
出力
250001000000

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。