No.312 置換処理

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

問題文

新人プログラマーである新人君は、プログラムに下記の2種類のコメントを記述している。
連続した2個分の#の後にコメントが書かれている通常のコメント
(例:## コメント
連続したN個分の#で書かれているプログラムの区切りコメント
(例:######### (N=9))

上司である貴方は、区切りコメントは不必要な為削除するように新人君に指導する必要がある。
新人君は既に大量の区切りコメントを書いており、手作業で1つずつ削除するのは非効率である。
その為、置換機能で区切りコメントを取り除くことにした。

置換機能とは、指定した文字列を別途指定した文字列に置き換える事である。
今回はいくつかの連続した#からなる文字列を空文字列(長さ0の文字列)に置き換えることで、区切りコメントを取り除く。

無駄が嫌いな貴方は置換を行う際にN個の#を書かなくても区切りコメントを空白に出来る場合があることに気が付いた。
例えば区切りコメントが######### (#9個分)で構成されていた場合には、### (#3個分)を空文字に置換することにより区切りコメントを完全に削除することが出来る。
新人君に対し、通常のコメントを消さずに区切りコメントを完全に消す置換を行う際に記述する必要がある最小の#の個数を教えてあげよう。

ただし、置換は1回しか行えないものとする。(複数回に分けて置換を行うことは出来ない)

入力

N

Nは 3 以上 1012 以下の整数で与えられます。

出力

通常のコメントを消さずに区切りコメントを完全に消す置換を行う際に記述する必要がある最小の#の個数を改行付きで出力せよ。

サンプル

サンプル1
入力
9
出力
3

問題文に書かれている例です。 #を3個毎に空文字へ置換することで、通常のコメントを消さずに区切りとしてのコメントを全て消すことが出来ます。

サンプル2
入力
30
出力
3

#を2個毎に空文字へ置換することでも区切りとしてのコメントを全て消すことが出来ますが、通常のコメントも消えてしまう為2個毎に置換することは出来ません。

サンプル3
入力
114514
出力
31

サンプル4
入力
8573912969
出力
421

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

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