問題一覧 > 通常問題

No.312 Replacement Processing

レベル : / AI推定難易度 : 700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 400
作問者 : iga_xx
お気に入りにしたユーザー ProblemId : 847 / 自分の提出
問題文最終更新日: 2026-06-25 15:38:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2015 (順位表) の他の問題:

Problem Statement

Shinjin-kun, a rookie programmer, writes the following two kinds of comments in his programs.
・A normal comment, in which the comment is written after 2 consecutive #
(Example: ## comment
・A separator comment of the program, written as N consecutive #
(Example: ######### (N=9))

You, as his boss, need to instruct Shinjin-kun to delete the separator comments because they are unnecessary.
Shinjin-kun has already written a large number of separator comments, and deleting them one by one by hand is inefficient.
Therefore, you decided to remove the separator comments using the replace function.

The replace function replaces a specified string with another specified string.
This time, the separator comments are removed by replacing a string consisting of some number of consecutive # with the empty string (a string of length 0).

Hating waste, you noticed that in some cases a separator comment can be made blank without writing N # characters when performing the replacement.
For example, if a separator comment consists of ######### (9 #), it can be completely deleted by replacing ### (3 #) with the empty string.
Tell Shinjin-kun the minimum number of # that must be written when performing a replacement that completely deletes the separator comments without deleting the normal comments.

However, the replacement can be performed only once. (The replacement cannot be split into multiple rounds.)

Input

N

N is given as an integer between 3 and 1012, inclusive.

Output

Output, followed by a newline, the minimum number of # that must be written when performing a replacement that completely deletes the separator comments without deleting the normal comments.

Sample

Sample 1
Input
9
Output
3

This is the example given in the problem statement. By replacing every 3 # with the empty string, all the comments serving as separators can be deleted without deleting the normal comments.

Sample 2
Input
30
Output
3

Replacing every 2 # with the empty string would also delete all the comments serving as separators, but it would delete the normal comments as well, so you cannot replace every 2 #.

Sample 3
Input
114514
Output
31

Sample 4
Input
8573912969
Output
421

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