/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
ストーリー
AtCoder社の倉庫には n 個のダンボール箱があり、m 個の山に分けて垂直に積まれている。 各箱には 1,\cdots,n の番号がちょうど一つずつ書かれており、番号の小さい方から1つずつ順番に倉庫から運び出したい。 ある箱を運び出すためには、その上に積まれている全ての箱を別の山へ移動させておく必要がある。 高橋社長はとても力持ちなので、積み重なった箱を一度に何箱でも持ち上げて動かすことが出来るが、持ち上げる箱の個数に応じて体力を消費してしまう。 出来るだけ体力消費が少なくなるような運び出し方を求めて欲しい。
問題文
1,\cdots,n の番号がちょうど一つずつ書かれた n 個のダンボール箱があり、m 個の山に分けて積まれている。 番号 v(1\leq v\leq n) の書かれた箱を「箱 v」、左から i(1\leq i\leq m) 番目の山を「山 i」と呼ぶことにする。 山の個数 m は n を割り切り、各山 i には n/m 個の箱が垂直に積まれており、箱の番号は下から順に b_{i,1},b_{i,2},\cdots,b_{i,n/m} である。
以下の2種類の操作を最大で 5000 回繰り返すことが出来る。
- まだ運び出されていない箱 v (1\leq v\leq n) を一つ選ぶ。箱 v とその上に積まれている全ての箱を現在の山から取り除き、別の山 i(1\leq i\leq m) の上へそのままの順序で移動する。箱 v の属する山 i' に積まれている箱が下から順に b_{i',1},\cdots,b_{i',h'}であり、b_{i',j}=v であったとする。また、移動先の山 i に積まれている箱が下から順に b_{i,1},\cdots,b_{i,h} であったとする。この操作後に山 i' は b_{i',1},\cdots,b_{i',j-1} となり、山 i は b_{i,1},\cdots,b_{i,h},b_{i',j},\cdots,b_{i',h'} となる。この操作により動かした箱の個数を k=h'-j+1 とすると、k+1 の体力を消費する。i=i'の場合、この操作により何も変化せず、ただ体力を浪費する。
- 残っている全ての箱の中で一番小さい番号が v であり、箱 v が山の一番上に積まれているならば、箱 v を外に運び出すことが出来る。この操作は体力を消費しない。
操作1で新たな山 i>m を作成することは出来ないが、操作 2 によって全ての箱が運び出されて空となった山 i(1\leq i\leq m) のスペースに操作1で箱を移動させることは可能である。
全ての箱を運び出す操作列であって、合計の体力消費量が出来るだけ少ないものを求めて欲しい。
得点
5000 回以下の操作回数で全ての箱を運び出すことが出来た場合、合計の体力消費量を V として、\max(1, 10000-V) の得点が得られる。 全ての箱を運び出すことが出来なかった場合や、不正な操作列(範囲外の値や既に運び出された箱を指定、もしくは操作2で条件を満たさない箱を指定)を出力した場合、WA と判定される。
合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。
入力
入力は以下の形式で標準入力から与えられる。
n m
b_{1,1} \cdots b_{1,n/m}
\vdots
b_{m,1} \cdots b_{m,n/m}
箱の個数 n と山の個数 m は全てのテストケースで n=200、m=10 で固定である。 b_{i,j} は山 i の下から j 番目の箱の番号を表し、1\leq b_{i,j}\leq n を満たす。
出力
k 回目の操作を2つの整数 (v_k,i_k) によって以下のように表す。
- 操作1を用いて箱 v(1\leq v\leq n) とその上に積まれている全ての箱を別の山 i(1\leq i\leq m) に移動する場合、(v_k,i_k)=(v,i)。
- 操作2を用いて箱 v を運び出す場合、(v_k,i_k)=(v,0)。
求めた操作列を (v_1,i_1),\cdots,(v_K,i_K) (K\leq 5000) としたとき、以下の形式で標準出力に出力せよ。
v_1 i_1 \vdots v_K i_K
入力生成方法
箱の番号は 1,\cdots,n の整数をランダムな順に並び替え、n/m個ずつに区切ることにより生成される。
ツール(入力ジェネレータ・ビジュアライザ)
- Web版: ローカル版より高性能でアニメーション表示が可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。
Story
AtCoder has n cardboard boxes in a warehouse, which are divided into m vertical stacks. Each box is labeled with a unique number from 1,\cdots,n, and CEO Takahashi wants to carry them out of the warehouse one by one in ascending order of their numbers. In order to carry out a box, he needs to move all the boxes on top of it to another stack. As Takahashi is a very strong man, he can lift and move as many boxes in a stack at a time, but he expends energy depending on the number of boxes he lifts. Please find a way to carry the boxes out that expends as little energy as possible.
Problem Statement
There are n cardboard boxes, each labeled with a unique number from 1,\cdots,n, divided into m stacks. We refer to the box labeled with the number v(1\leq v\leq n) as "box v" and the i(1\leq i\leq m)-th stack from the left as "stack i". The number of stacks m is a divisor of n, and each stack i contains n/m boxes, with numbers b_{i,1},b_{i,2},\cdots,b_{i,n/m} from bottom to top.
You can repeat the following two types of operations up to 5000 times.
- Choose one box v (1\leq v\leq n) that has not yet been carried out. Remove box v and all boxes above it from the current stack and move them to the top of another stack i(1\leq i\leq m) in the same order. Assume that in the stack i' to which box v belongs, the boxes are numbered b_{i',1}, \cdots, b_{i',h'} from bottom to top, with b_{i',j} = v. Also, assume that the boxes in the destination stack i are numbered b_{i,1}, \cdots, b_{i,h} from bottom to top. After this operation, stack i' will become b_{i',1}, \cdots, b_{i',j-1}, and stack i will become b_{i,1}, \cdots, b_{i,h}, b_{i',j}, \cdots, b_{i',h'}. Let the number of boxes moved by this operation be k = h' - j + 1. Then, k+1 units of energy will be expended. If i=i', this operation changes nothing and just wastes energy.
- If the smallest number among all the remaining boxes is v, and box v is at the top of a stack, then box v can be carried out. This operation does not expend energy.
Operation 1 cannot create a new stack i>m, but it can move boxes into an empty stack i(1\leq i\leq m) after all boxes have been carried out from it by operation 2.
Please find a sequence of operations that carries out all the boxes with as little total energy expenditure as possible.
Scoring
If all the boxes are carried out with less or equal to 5000 operations, and the total energy expenditure is V, you will obtain a score of \max(1, 10000-V). If you failed to carry out all the boxes, or if you output an illegal operation sequence (specifying out-of-range values or a box that has already been carried out, or specifying a box that does not satisfy the condition in operation 2), it is judged as WA.
There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.
Input
Input is given from Standard Input in the following format:
n m
b_{1,1} \cdots b_{1,n/m}
\vdots
b_{m,1} \cdots b_{m,n/m}
The number of boxes n and the number of stacks m are fixed at n=200 and m=10 in all the test cases. The number b_{i,j} represents the number of the j-th box from the bottom of stack i, and satisfies 1\leq b_{i,j}\leq n.
Output
Let the k-th operation be represented by the two integers (v_k,i_k) as follows.
- If you use operation 1 to move box v(1\leq v\leq n) and all the boxes stacked on it to another stack i(1\leq i\leq m), then (v_k,i_k)=(v,i).
- If you use operation 2 to carry out box v, (v_k,i_k)=(v,0).
Output the obtained sequence of operations (v_1,i_1),\cdots,(v_K,i_K) (K\leq 5000) to Standard Output in the following format:
v_1 i_1 \vdots v_K i_K
Input Generation
The box numbers are generated by randomly shuffling the integers from 1 to n and then dividing them into groups of n/m each.
Tools (Input generator and visualizer)
- Web version: This is more powerful than the local version providing animations.
- Local version: You need a compilation environment of Rust language.
- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.
Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.