No.2426 Select Plus or Minus
Problem Statement
You are given an integer $N$ that is at least $2$. There is a variable $m$, initially $m=N$.
In $1$ operation, you can do the following to the variable $m$.
- If $m$ is even, replace $m$ with $m/2$.
- If $m$ is odd, choose one of $3m+1, 3m-1$ and replace $m$ with it.
Construct $1$ sequence of operations that satisfies all of the following $3$ conditions. It is guaranteed that such a sequence of operations exists under the constraints of the problem.
- The number of operations is at most $10000$.
- After all operations are finished, $m=1$ holds.
- The value of $m$ after each operation does not exceed $10^{18}$.
Constraints
- $2 \le N \le 10^{15}$
- $N$ is an integer.
Input
$N$
Output
Output a sequence of operations satisfying all $3$ conditions in the problem statement, in the following format.
$K$ $c_1 c_2\cdots c_K$
On line $1$, output an integer $K \ (1 \le K \le 10000)$ representing the number of operations.
On line $2$, output $K$ characters. Character $i$ represents the $i$-th operation to perform, and the output character $c_i$ must be as follows.
-
/: the operation that replaces $m$ with $m/2$ when $m$ is even -
+: the operation that replaces $m$ with $3m+1$ when $m$ is odd -
-: the operation that replaces $m$ with $3m-1$ when $m$ is odd
Sample
Sample 1
Input
7
Output
8 +/-/////
The variable $m$ is initially $m = 7$. With this output, the operations are performed as follows, and the $3$ conditions are satisfied.
After operation $1$, $m = 3 \times 7 + 1 = 22$.
After operation $2$, $m = 20 / 2 = 11$.
After operation $3$, $m = 3 \times 11 - 1 = 32$.
After operation $4$, $m = 32 / 2 = 16$.
After operation $5$, $m = 16 / 2 = 8$.
After operation $6$, $m = 8 / 2 = 4$.
After operation $7$, $m = 4 / 2 = 2$.
After operation $8$, $m = 2 / 2 = 1$.
Any sequence of operations that satisfies the conditions is acceptable, so the following output is also accepted. Note that you do not need to minimize the number of operations.
23 +/+/-/+//+/+///-/////-/
Sample 2
Input
5
Output
5 +////
Sample 3
Input
7217572745
Output
100 +//-//-/-////+/-/-//-/-////-/-/+//-////+///////-//+////-////+///+//-//////+/////+/+////+////-//+////
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
0214sh7
noya2