← 返回题目列表

AtCoder · joisc2007_circui

circuit. 电路接线(电路)

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

電気回路の結線 (Circuit) - 原题 PDF 第 1 页
原题PDF第4页
電気回路の結線 (Circuit) - 原题 PDF 第 2 页
原题PDF第5页
可复制的 PDF 提取文本
Circuit: 電気回路の結線


input ファイル“circuit.in”
output 標準出力
ソースファイルcircuit.c/circuit.cpp/Circuit.java
時間制限1 秒/ データ


  n 個の入力とn 個の出力を持つ,次の図のようなIC (集積回路) を考える.n 個の入力には

左から1, 2, . . . , n と番号が振られている.同様にn 個の出力にも左から1, 2, . . . , n と番号が振

られている.

                    入力                                       z    }|    {
                                    1  2    n
                                                                         · · ·


                                                                         · · ·
                                    1  2    n                                       |    {z    }
                    出力


 このIC では,n 個の入力の各々がそのままn 個の出力となって出てくるのだが,どの入力

がどの出力に対応しているかはわからない.IC は出力1, . . . , n に対応する入力の番号を並べる

ことで記述する.

 例えば,n = 3 のとき,次の6 種類のIC が存在する.





                        IC (1, 2, 3)  IC (1, 3, 2)  IC (2, 1, 3)





                        IC (2, 3, 1)  IC (3, 1, 2)  IC (3, 2, 1)

 ここで,IC (2, 3, 1) を5 個直列につなぐと,次の図のように最初の入力3, 1, 2 がそれぞれ最

後の出力1, 2, 3 に対応するので,結局IC (3, 1, 2) と同じ動作をすることになる.





                    電気回路の結線–1/2

整数n (1 ≦n ≦10000), k (1 ≦k ≦10000) と1 からn までの異なる整数の列a1, . . . , an が
与えられたとき,同じ種類のIC をk 個直列につなぐことでIC (a1, . . . , an) と同じ動作をさせ
ることができるかどうかを判定し,できる場合には目的を達成できるIC を出力するプログラ

ムを書け.条件に合うIC が複数存在するときは, どのIC を出力してもよい.

Input.

 入力ファイルcircuit.in はn + 1 行からなる.

  1 行目には整数n とk が空白で区切って書かれている.
   i + 1 行目(1 ≦i ≦n) には整数ai が書かれている.

Output.

 プログラムは結果を標準出力に出力する.
 同じ種類のIC をk 個直列につないでIC (a1, . . . , an) と同じ動作をさせることが可能な場合,
1 行目からn 行目までのn 行で条件を満たすIC を記述せよ.すなわち,1 ≦i ≦n に対し,i

行目にはIC の出力i に対応する入力の番号を書け.
 同じ種類のIC をk 個直列につないでIC (a1, . . . , an) と同じ動作をさせることが不可能な場
合,0 と書いた1 行だけを出力せよ.

 例1                 例2
   circuit.in 標準出力             circuit.in 標準出力
   3 5         2                   4 4         0
   3           3                   2
   1           1                   1
   2                               4
                                   3



                    電気回路の結線–2/2