ストーリー
発明家のTERRYくんは、電子デバイスに対してチューニングを行って性能を向上させることのできる装置「TUNER amp 2026」を開発した。この装置は汎用性が考慮されており、アダプタを付け替えることでどんな電子デバイスのチューニングも行うことができる。アダプタの付け替えには、付け替え前後のアダプタのペアに対応した時間がかかり、使うアダプタの順番を工夫することで作業時間を短縮することができる。噂を聞きつけた人々から多数のオーダーが届いているため、できるだけ早く全てのオーダーが完了するような計画を立ててほしい。
問題文
\(N\) 個のオーダーと\(M+1\) 個のアダプタがある。オーダーは \(0, \cdots, N - 1\) 、アダプタは \(0, \cdots, M\) と番号が付けられている。
装置は一度に \(1\) つのアダプタのみ取り付け可能であり、オーダー \(i\) は装置にアダプタの集合 \(S_i=\lbrace s_{i,0},\cdots,s_{i,K-1}\rbrace\) のいずれかの要素を取り付けることによって遂行することができる。オーダーの遂行にかかる時間は無視できるが、アダプタ \(i\) からアダプタ \(j\) に取り替えるときには \(t_{i,j}\ (0\le i,j\le M)\) 秒の時間がかかる。アダプタ \(M\) はオーダーを遂行することはできないが、初期状態と終了状態は必ずアダプタ \(M\) が取り付けられている状態でなければならない。
アダプタの取り付け順を \(P=(P_0, P_1, \cdots, P_{N+1})\) 、オーダーの遂行順を \(Q=(Q_1, \cdots, Q_N)\) とすると、 \(P_0=P_{N+1}=M\) かつ \(P_k\in S_{Q_k}\ (k=1,\cdots,N)\) でなければならない。このとき、総所要時間 \(T\) は \(T=\sum_{k=0}^N{t_{P_k, P_{k+1}}}\) 秒となる。全てのオーダーをちょうど \(1\) 回ずつ遂行し、総所要時間 \(T\) ができるだけ短くなるような取り付け順とオーダーの遂行順を求めよ。
入力は以下の形式で標準入力から与えられる。 \(t\) は \((M+1)\times(M+1)\) 行列で与えられることに注意せよ。
なお、 \(C\) は得点計算に用いられる定数である。詳細は Scoring セクションを参照せよ。
| \(N\) \(M\) \(K\) \(C\) |
| \(t_{0,0}\) \(\cdots\) \(t_{0,M}\) |
| \(\vdots\) |
| \(t_{M,0}\) \(\cdots\) \(t_{M,M}\) |
| \(s_{0,0}\) \(\cdots\) \(s_{0,K-1}\) |
| \(\vdots\) |
| \(s_{N-1,0}\) \(\cdots\) \(s_{N-1,K-1}\) |
ここで、入力は以下の制約を満たす。
アダプタの取り付け順 \(P\) およびオーダーの遂行順 \(Q\) を以下の形式で \(N+2\) 行にわたって標準出力に出力せよ。
| \(P_0\) |
| \(P_1\) \(Q_1\) |
| \(\vdots\) |
| \(P_N\) \(Q_N\) |
| \(P_{N+1}\) |
ただし、出力は以下の条件を全て満たさなければならない。
総所要時間が \(T\) 秒であるとき、入力で与えられる定数 \(C\) を用いて \(\max(C - T,1)\) 点が得られる。
不正な出力や制限時間超過をした場合、そのテストケースのスコアは 0 点となる。テストケースは全部で 50 個あり、各テストケースの得点の合計が提出の得点となる。
入力生成方法
\(L\) 以上 \(U\) 未満の実数値を一様ランダムに生成する関数を \(\mathrm{randdouble}(L,U)\) と表して、以下のように生成する。
ツール(入力ジェネレータ・ローカルテスタ・ビジュアライザ)