2007-day3-circuit-prob - 情報オリンピック攻略Wiki

電気回路の結線 (Circuit)

---

時間制限 : 1sec / スタック制限 : 64MB / メモリ制限 : 64MB

---

　n 個の入力とn 個の出力を持つ，次の図のようなIC (集積回路) を考える．n 個の入力には左から1, 2, … , n と番号が振られている．同様にn個の出力にも左から1, 2, … , n と番号が振られている．

　このIC では，n 個の入力の各々がそのままn 個の出力となって出てくるのだが，どの入力がどの出力に対応しているかはわからない．IC は出力1, … , n に対応する入力の番号を並べることで記述する．
　例えば，n = 3 のとき，次の6 種類のIC が存在する．

　ここで，IC (2, 3, 1) を5 個直列につなぐと，次の図のように最初の入力3, 1, 2 がそれぞれ最後の出力1, 2, 3 に対応するので，結局IC (3, 1, 2) と同じ動作をすることになる．

整数n (1 ≦ n ≦ 10000), k (1 ≦ k ≦ 10000) と1 からn までの異なる整数の列a₁, … , a_n が与えられたとき，同じ種類のIC をk 個直列につなぐことでIC (a₁, … , a_n) と同じ動作をさせることができるかどうかを判定し，できる場合には目的を達成できるIC を出力するプログラムを書け．条件に合うIC が複数存在するときは, どのIC を出力してもよい．

入力

　入力ファイルcircuit.in はn + 1 行からなる．
　1 行目には整数n とk が空白で区切って書かれている．
　i + 1 行目(1 ≦ i ≦ n) には整数a_i が書かれている．

出力

　プログラムは結果を標準出力に出力する．
　同じ種類のIC をk 個直列につないでIC (a₁, … , a_n) と同じ動作をさせることが可能な場合，1 行目からn 行目までのn 行で条件を満たすIC を記述せよ．すなわち，1 ≦ i ≦ n に対し，i 行目にはIC の出力i に対応する入力の番号を書け．
　同じ種類のIC をk 個直列につないでIC ({a₁, … , a_n) と同じ動作をさせることが不可能な場合，0 と書いた1 行だけを出力せよ．

入出力例

入力例1	出力例1
3 5 3 1 2	2 3 1

入力例2	出力例2
4 4 2 4 1 3	0

コメント