問題一覧 > 通常問題

No.3183 Swap or Rotate

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 75
作問者 : 蜜蜂 / テスター : Mitarushi
ProblemId : 12272 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-06-15 12:53:42

問題文

$(0, 1, 2, \cdots, N - 1)$ の順列 $P = (P_0, P_1, \cdots, P_{N - 1})$ が与えられます.
あなたの目標は $P = (0, 1, 2, \cdots, N - 1)$ とすることです.そのために,以下の $2$ つの操作を $20000$ 回まで好きな順番で行うことができます.

  • $P_0$ と $P_1$ を交換する.
  • $i = 0, 1, \cdots, N - 1$ について $P_i$ を一斉に $P_{(i + 1) \ \mathrm{mod} \ N}$ で置き換える.
制約下であなたの目標は必ず達成できることが証明できます.目標を達成する操作列の一例を出力してください.なお,操作の回数を最小化する必要はありません.

入力

$N$
$P_0 \ P_1 \ \cdots P_{N - 1}$

  • $3 \leq N \leq 100$
  • $P$ は $(0, 1, 2, \cdots, N - 1)$ の順列
  • 入力はすべて整数

出力

$M$ 回の操作で目標を達成できる場合,$M$ 文字の文字列を出力してください.$i$ 文字目について,$i$ 回目の操作で $P_0$ と $P_1$ を交換する操作をする場合 S と,そうでない場合 R としてください.
条件を満たす操作列が複数存在する場合,いずれを出力しても構いません.

サンプル

サンプル1
入力
4
3 1 0 2
出力
SSRS

  • $1$ 回目の操作の後,$P = (1, 3, 0, 2)$ となります.
  • $2$ 回目の操作の後,$P = (3, 1, 0, 2)$ となります.
  • $3$ 回目の操作の後,$P = (1, 0, 2, 3)$ となります.
  • $4$ 回目の操作の後,$P = (0, 1, 2, 3)$ となります.

サンプル2
入力
3
0 1 2
出力


            

操作を行わずとも目標が達成できている場合,空文字列を出力しても構いません.

サンプル3
入力
3
2 1 0
出力
SRR

RS などを出力しても正解とみなされます.

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