問題一覧 > 通常問題

No.71 そろばん

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 335
作問者 : yuki2006yuki2006
1 ProblemId : 140 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:46:49

問題文

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

一般的なそろばんは、一列だけ見ると、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

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