No.2426 Select Plus or Minus
タグ : / 解いたユーザー数 148
作問者 :
shobonvip
/ テスター :
0214sh7
noya2
👑 
potato167
tassei903
ramdos
ponjuice
問題文
$2$ 以上の整数 $N$ が与えられます。変数 $m$ があり、最初は $m=N$ です。
あなたは変数 $m$ に対して、$1$ 回の操作で次を行うことができます。
- $m$ が偶数のとき、$m$ を $m/2$ に置き換える。
- $m$ が奇数のとき、$3m+1, 3m-1$ の片方を選び、 $m$ をそれに置き換える。
次の $3$ つの条件をすべて満たすような操作列を $1$ つ構築してください。ただし、問題の制約下でそのような操作列が存在することが保証されます。
- 操作回数は $10000$ 以下である。
- 操作をすべて終えた後は $m=1$ となっている。
- 各操作後の $m$ は $10^{18}$ を超えない。
制約
- $2 \le N \le 10^{15}$
- $N$ は整数
入力
$N$
出力
次の形式に従って、問題文の $3$ つの条件をすべて満たす操作列を出力してください。
$K$ $c_1 c_2\cdots c_K$
$1$ 行目には、操作回数を表す整数 $K \ (1 \le K \le 10000)$ を出力してください。
$2$ 行目には、 $K$ 文字出力してください。 $i$ 文字目は $i$ 番目に行う操作を表し、出力する文字 $c_i$ は次に従ってください。
-
/：$m$ が偶数で、 $m$ を $m/2$ に置き換える操作 -
+：$m$ が奇数で、 $m$ を $3m+1$ に置き換える操作 -
-：$m$ が奇数で、 $m$ を $3m-1$ に置き換える操作
サンプル
サンプル1
入力
7
出力
8 +/-/////
変数 $m$ は最初 $m = 7$ です。この出力では操作は次のようにして行われ、$3$ つの条件を満たします。
$1$ 回目の操作の後は $m = 3 \times 7 + 1 = 22$ になる。
$2$ 回目の操作の後は $m = 20 / 2 = 11$ になる。
$3$ 回目の操作の後は $m = 3 \times 11 - 1 = 32$ になる。
$4$ 回目の操作の後は $m = 32 / 2 = 16$ になる。
$5$ 回目の操作の後は $m = 16 / 2 = 8$ になる。
$6$ 回目の操作の後は $m = 8 / 2 = 4$ になる。
$7$ 回目の操作の後は $m = 4 / 2 = 2$ になる。
$8$ 回目の操作の後は $m = 2 / 2 = 1$ になる。
条件を満たす操作方法ならよいので、次のような出力も認められます。操作回数を最小化する必要がないことに注意してください。
23 +/+/-/+//+/+///-/////-/
サンプル2
入力
5
出力
5 +////
サンプル3
入力
7217572745
出力
100 +//-//-/-////+/-/-//-/-////-/-/+//-////+///////-//+////-////+///+//-//////+/////+/+////+////-//+////
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。