Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 点
問題文
時は 20XX 年,世界は Distributed AtC◯der 社の支配によるディストピアである.現在,人々の娯楽は分散・並列処理を題材としたプログラミングコンテストに限られている.例えば,週末に家族でスーパーコンピュータを (ssh で) 訪れるというのはとてもよく見られる光景である. (問題文参考: UTPC 2011 問題 A)
(実際のところ以下で述べる問題設定は分散というより並列処理で Distributed Sorting というより Parallel Sorting っぽいのだが,頭文字が D の方が都合がいいし,ここで言い訳もしていることだし,とにかく今日はクリスマスなので我々は細かいことは気にしない.)
分散・並列処理においては,基礎的と思える処理でも多種多様な工夫が考えられることが多くある.たとえば, 個の相異なる整数からなる整数列 , , ..., を昇順にソートする処理を考えよう.
ソートには,以下の 種類の操作が可能なマシンを用いるとする.
- 操作: 個の相異なるインデックス , , ..., を入力として与えると,各 () に対し と ( の 番目と 番目) の値を交換する.ただし,各 () に対し でなければならない.
たとえば のとき , として操作を行うと, になる.
この操作だけを使って を昇順にソートするために必要な操作の最小回数を求め,実際にその最小回数の操作で をソートする手順をひとつ出力するようなプログラムを作成せよ.
制約
- .
- .
- は相異なる整数.
入力
入力は以下の形式で標準入力から与えられる.
...
出力
行目に を昇順にソートするために必要な操作の最小回数を出力し,それに続いて,各操作の内容を 操作につき 行で出力せよ.
操作を表す行の最初には,値の交換を行うペア数 を出力せよ.その後,空白に続いて 個の整数 , , ..., を空白区切りで出力せよ.
入力例 1Copy
3 2 3 1
出力例 1Copy
2 1 1 3 1 2 3
操作の回数が最小であり,正しく昇順にソートできるような手順であれば,これ以外の出力でも正解と見なされる.たとえばこの入力例に対しては
2 1 1 2 1 3 1
のような出力も正解と見なす.
入力例 2Copy
3 1 2 3
出力例 2Copy
0
入力例 3Copy
5 5 4 3 2 1
出力例 3Copy
1 2 1 5 2 4