/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 7 点
注意
この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
初期値が 1 の変数 X があります。
高橋君は、変数 X に対して、「 X を 3 倍する」という操作を 30 回行いました。 しかし、操作の結果 X は 3^{30} とはならず、N という値になってしまいました。
いたずら好きな青木君が、以下の操作をしたことを白状しました。
- 1 \leq k \leq 30 であるような整数 k を 1 つだけ選び、高橋君の k 回目の操作の直後に変数 X に 1 を加算した。
N が与えられるので、k を求めてください。 ただし、どのような k に対しても操作の結果として X が N とはならない場合、-1 と出力してください。
制約
- 1 \leq N \leq 10^{15}
- N \neq 3^{30}
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。 ただし、どのような k に対しても操作の結果 X が N とはならない場合、-1 と出力せよ。
入力例 1
205894618879050
出力例 1
10
k=10 の場合の挙動を示します。
1 を 10 回 3 倍すると 59049 になります。 青木君のいたずらにより 1 を加算して 59050 になります。
さらに、20 回 3 倍すると 205894618879050 になります。
入力例 2
314159265358979
出力例 2
-1
Score : 7 points
Warning
Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
We have a variable X whose initial value was 1.
Takahashi did 30 operations on this variable, where each operation multiplied X by 3. However, it did not result in X being 3^{30}, but it became N, a different value.
A mischievous boy Aoki has confessed that he did the following:
- He chose a integer k such that 1 \leq k \leq 30 and added 1 to X just after the k-th operation by Takahashi.
Given N, find k. Here, if no choice of k would result in X being N after the operations, print -1.
Constraints
- 1 \leq N \leq 10^{15}
- N \neq 3^{30}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer. If no choice of k would result in X being N after the operations, print -1.
Sample Input 1
205894618879050
Sample Output 1
10
Let us simulate the process for the case k=10.
Multiplying 1 by 3 ten times results in 59049. Then, Aoki mischievously adds 1 to it, resulting in 59050.
Multiplying that value by 3 twenty more times results in 205894618879050.
Sample Input 2
314159265358979
Sample Output 2
-1