問題一覧 > 通常問題

No.2426 Select Plus or Minus

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 150
作問者 : shobonvip / テスター : 0214sh7 noya2 👑 potato167 tassei903 ramdos ponjuice
お気に入りにしたユーザー ProblemId : 9994 / 自分の提出
問題文最終更新日: 2023-08-14 18:07:09
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
traP 作問ハッカソンコンテスト 001 (順位表) の他の問題:

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.

  1. The number of operations is at most $10000$.
  2. After all operations are finished, $m=1$ holds.
  3. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。