問題一覧 > 通常問題

No.3183 Swap or Rotate

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 87
作問者 : 蜜蜂 / テスター : 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もしくは右上の雲マークをクリックしてアカウントを作成してください。