Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
この問題はインタラクティブ形式です。
Xは神経衰弱で遊ぶこととマラソンをすることが大好きです。ある日、Xは神経衰弱と長距離走を組み合わせた新たなゲームで遊ぶことにしました。
\(1\) 以上 \( \lfloor N/2 \rfloor \) 以下の整数がひとつ書かれているカードを大量に用意し、シャッフル後に裏向きに積んで作られた山札が \(N\) 個あります。
山札は横一列に等間隔で並んでいて、左から順に山札 \(0, 1, \cdots, N-1\) とします。
Xは山札の上を動き回り、二連続で同じ値のカードを見たらそれらのカードをペアで取り除いてスコアを獲得します。
ゲーム開始時、Xは山札 \(0\) の上にいて、初期スコアは \(0\) です。
Xは、移動可能な総距離 \(T\) を超えない範囲で以下の一連の操作を繰り返し行うことができます。
- 操作開始時にXがいる山札の番号を \(p\) とします。
- 山札 \(p\) の一番上のカードが表向きであれば、その整数を \(a_p\) とします。 （一番最初の操作時、および、後述のペアで取り除いた直後の移動時は、山札 \(p\) の一番上のカードは裏向きです。）
- 山札 \(q ( 0 \leq q \leq N-1) \) をひとつ選び、 山札 \(p\) から山札 \(q\) の上に移動します。（ \(q = p\) でもかまいません。）この時の移動距離は \(|p - q|\) です。
- 山札 \(q\) の一番上のカードを表向きにし、そのカードに書かれている整数を \(a_q\) とします。
- 表向きで存在する二枚のカードの値が等しい場合は、そのカードをペアで取り除いてカードに書かれた整数分のスコアを得ます。つまり、\(p \neq q\) かつ\( a_p = a_q \) の場合、山札 \(p, q\) の一番上からカードを1枚ずつ取り除き、スコアが \(a_p\) だけ加点されます。カードを取り除いた後のそれぞれの山札の一番上には、必ず新たなカードが裏向きで存在します。
- ペアで取り除けなかった場合、表向きで存在するカードが二枚あれば、先に表向きにしたカードが裏向きに戻ります。つまり、 \(p \neq q\)の時に、山札 \(p\) の一番上のカードが裏向きになります。
Xが得るスコアがなるべく大きくなるようにXを動かしてください。
各テストケースの得点およびこの問題の得点は、次のように計算されます。
- 1つのテストケースでは、Xが得たスコアの合計がそのまま得点になります。
- テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。
入出力
最初に、以下の形式で標準入力から入力が与えられます。
\(N\) \(T\)
- N は山札の個数を表す整数で、N = 50 を満たします。
- T は移動可能な総距離を表す整数で、T = 10000 を満たします。
- ジャッジプログラムの都合上、標準入力の内容を必ず読み込んでください。
以降、次のやり取りをジャッジプログラムと繰り返し行ってください。
1. 標準出力に整数をひとつ出力してください。
\(q\)
- Xを移動させる場合、Xが移動する先の山札の番号を表す整数 \((0 \leq q \leq N-1)\) を出力してください。
- ゲームを終了する場合は
-1を出力してプログラムを終了してください。 - 移動可能な総距離を超える移動をした場合はWrong Answerとなります。
- 出力の後には必ず改行し、flush してください。
2. \(q \neq -1\) の場合、標準入力から整数がひとつ与えられます。
\(a_q\)
- a_q は、山札 \(q\) の一番上のカードに書かれている整数 \((1 \leq a_q \leq N/2)\) を表します。
- ジャッジプログラムの都合上、標準入力の内容を必ず読み込んでください。
テストケースの生成について
各カードに書かれた整数は一様乱数にしたがって生成されます。
入出力例
| プログラムへの入力 | プログラムの出力 | 説明 | 山札の情報 | 移動 総距離 |
スコア |
|---|---|---|---|---|---|
4 6 |
山札が4個あり、移動可能な総距離が6であることを表します。 このサンプルは制約 \(N=50\) および \(T=10000\) を満たしていません。 |
? ? ? ? |
0 | 0 | |
0 |
山札0に移動して一番上のカードを表向きにします。 最初にXは山札0の上にいるので、移動距離は0です。 |
? ? ? ? |
0 | 0 | |
1 |
山札0の一番上には1と書かれたカードがあります。 |
1 ? ? ? |
0 | 0 | |
2 |
山札2に移動します。山札0から山札2への移動距離は2です。 | 1 ? ? ? |
2 | 0 | |
2 |
山札2の一番上には2と書かれたカードがあります。 \(a_0 \neq a_2\) なので、先に表向きにした山札0の一番上のカードは裏向きになります。 |
1 ? 2 ?↓ ? ? 2 ? |
2 | 0 | |
1 |
山札1に移動します。山札2から山札1への移動距離は1です。 | ? ? 2 ? |
3 | 0 | |
2 |
山札1の一番上には2と書かれたカードがあります。 \(a_1 = a_2 = 2\) なので、山札1,2からカードを取り除き、スコアを2点獲得します。 山札1, 2からカードを取り除いたことで、それぞれの山札の一番上にあるカードは再度表向きにしないと分かりません。 |
? 2 2 ?↓ ? ? ? ? |
3 | 2 | |
1 |
今いる山札1の一番上のカードを表向きにします。 | ? ? ? ? |
3 | 2 | |
2 |
山札1の一番上には2と書かれたカードがあります。 先ほどと同じ整数が出ることもあります。 |
? 2 ? ? |
3 | 2 | |
2 |
山札1から山札2へ移動します。 | ? 2 ? ? |
4 | 2 | |
1 |
山札2の一番上には1と書かれたカードがあります。 | ? 2 1 ?↓ ? ? 1 ? |
4 | 2 | |
0 |
山札2から山札0へ移動します。 | ? ? 1 ? |
6 | 2 | |
1 |
山札0の一番上には（一度表向きにしたことからすでに判明しているように）1と書かれたカードがあり、条件を満たすのでペアで取り除いてスコアを1点獲得します。 | 1 ? 1 ?↓ ? ? ? ? |
6 | 3 | |
-1 |
ゲームを終了します。さらに移動しようとすると、移動可能な総距離を超えてしまいWrong Answer扱いとなります。 | ? ? ? ? |
6 | 3 |
テスター
次のリンクから提供しています。
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
パズル愛好家のXは、自ら考案した新しいパズルを解こうとしています。
Xの考案したパズルは N × N のグリッドからなっており、一番左上、右上、左下、右下のセルの座標をそれぞれ (0,\ 0),\ (0,\ N-1),\ (N-1,\ 0),\ (N-1,\ N-1) と表します。
ここで、グリッド内のあるセルの座標を (r,\ c) としたとき、下記に定義されるいずれかの領域にあると呼ぶことにします。
- \(r < N/2\) かつ \(c < N/2\) ならば、左上領域。
- \(r < N/2\) かつ \(c \geq N/2\) ならば、右上領域。
- \(r \geq N/2\) かつ \(c < N/2\) ならば、左下領域。
- \(r \geq N/2\) かつ \(c \geq N/2\) ならば、右下領域。
このパズルでは以下の操作を行うことができます。
- グリッド内のある正方形のサブグリッドを選択し、その内部を時計回りに90度回転させる。
上記操作を最大 M 回まで行って、グリッドの左上領域に赤を、右上領域に黄を、左下領域に緑を、右下領域に青を集めるのがこのパズルの目標です。
パズルを考案するのは得意でも解くのは苦手なXの代わりに、どういう操作を行えばよいか考えてあげてください。
各テストケースの得点および、この問題の得点は、次のように計算されます。
- 1つのテストケースの得点は、次のように計算されます。
- すべての操作が終了したグリッドで、
\({\it 左上領域にある赤セル数}\ +\ \)\({\it 右上領域にある黄セル数}\ +\ \)\({\it 左下領域にある緑セル数}\ +\ \)\({\it 右下領域にある青セル数}\)
を得点とする。 - すべての赤セルが左上領域に、黄セルが右上領域に、緑セルが左下領域に、青セルが右下領域に集まっている場合、これを完全解と呼び、\(M - {\it 操作回数}\) を得点に加える。
- テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
N M
c_{0,0} c_{0,1} \(\cdots\) c_{0,N-1}
\(\vdots\)
c_{N-1,0} c_{N-1,1} \(\cdots\) c_{N-1,N-1}
- N はグリッドの縦と横の長さを表す整数で、N=20 を満たします。
- M は操作の最大回数を表す整数で、M=1000 を満たします。
- c_{i,j} は座標 (i,\ j) のセルの初期状態を表す整数で、0=赤, 1=黄, 2=緑, 3=青 と対応します。
出力
行う操作を各行に１つずつ順番に標準出力に出力してください。
ここで、r_{i},\ c_{i} はサブグリッドの一番左上のセルの座標 (r_{i},\ c_{i}) を表し、s_{i} はサブグリッドの辺の長さを表します。
r_{0} c_{0} s_{0}
\(\vdots\)
r_{i} c_{i} s_{i}
\(\vdots\)
テストケースの生成について
各テストケースは、完全解の状態からランダムな正方形のサブグリッドを選択して反時計回りに90度回転させるのを1000回行ったものになります。
すなわち、1000回以内の操作で完全解にできることが保証されています。
入力例1
4 1000 3 2 3 2 3 3 1 0 1 1 0 1 0 0 2 2
注意: この入力はテストケースとしての制約を満たしていません。
出力例1
0 0 3 0 1 3 1 1 2 0 0 4
初期状態から最終操作後までの各グリッドのビジュアライズ結果を以下に図示しています。
完全解を達成しているので、このサンプルでの得点は、\(4 + 4 + 4 + 4 + (1000 - 4) = 1012\) になります。
ジェネレータとテスターとサンプル入力データ
テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。
ヒント：サブグリッドを回転させる処理は、テスターの中に実装があります。参考にしてください。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。