Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
この問題はインタラクティブ形式です。
Xはすごろく遊びが大好きで、毎日ひとりですごろく遊びをしています。
ある日、Xは普通のすごろくはマスの内容があらかじめわかっているのがつまらないと感じ、新たなすごろくゲームで遊ぶことにしました。
- このすごろくは1列に並んだ \(N + 1\) マスからなっています。
- マスには順に \(0, 1, ..., N\) と番号が振られています。\(0\) 番目のマスがスタートで、\(N\) 番目のマスがゴールです。
-
サイコロを振ってその出目の値だけゴールに向かって進みます。
ゴールを通り過ぎる場合は、通り過ぎたぶんスタート方向へ折り返します。（具体的には入出力例をご覧ください） - ゴールにぴったり到達したら、またスタートからゴールを目指すのを繰り返します。
- \(i\) 番目のマスには整数 \(V_i\) が書かれていて、マスに止まるとそこに書かれている整数がスコアとして加算されます。
- 一度ゴールに到達して再スタートしたあとも \(V_i\) の値は変わりませんが、\(i\) 番目のマスにはじめて止まるまでは \(V_i\) の値はわかりません。
- ゲーム開始時、Xはスタートにいて、初期スコアは \(0\) です。
Xはサイコロを \(M\) 回振って遊ぶことにしましたが、ゲームをより面白くするためにサイコロにも一工夫を加えることにしました。
- Xが使うサイコロは、偏りのない6面サイコロで、各面の値は\(1, 2, 3, 4, 5, 6\)となっています。
- Xは毎回サイコロを振る前に、サイコロのどれかひとつの面を \(1 \sim 6\) の好きな整数に変えることができます。サイコロの目の変化はそれ以降も継続します。
どうサイコロの目を設定したらよいかわからないXのかわりに、
Xが得るスコアがなるべく大きくなるように、サイコロの目を設定しながらすごろく遊びをしてください。
各テストケースの得点およびこの問題の得点は、次のように計算されます。
- 1つのテストケースでは、Xが得たスコアがそのまま得点になります。
- テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。
入出力
最初に、以下の形式で標準入力から入力が与えられます。
\(N\) \(M\)
- N はスタートを除いたすごろくのマス目の個数を表す整数で、N = 500 を満たします。
- M はサイコロを振る回数を表す整数で、M = 5000 を満たします。
- ジャッジプログラムの都合上、標準入力の内容を必ず読み込んでください。
以降、次のジャッジプログラムとのやり取りを M 回繰り返し行ってください。
M 回のやり取りが終了したら、プログラムを終了してください。
1. 標準出力に整数を6つ出力してください。
\(d_0\) \(d_1\) \(d_2\) \(d_3\) \(d_4\) \(d_5\)
- \(d_0, ..., d_5\) は、次に振るサイコロの各面の値で、前回のサイコロの各面と比較して、たかだか1要素まで異なってよいです。
- ゲーム開始時、 \((d_0, d_1, d_2, d_3, d_4, d_5) = (1, 2, 3, 4, 5, 6)\) です。
- 前回のサイコロの各面の値と2要素以上異なる場合や、各面の値が \(1 \sim 6\) でない場合は Wrong Answer となります。
- 出力の後には必ず改行し、flush してください。
2. 標準入力から整数が3つ与えられます。
\(d\) \(v\) \(x\)
- d は、サイコロの出目を表します。
- v は、サイコロによって到達したマスに書かれた値を表します。
- x は、サイコロによって最終的に到達したマスの番号を表します。ゴールに到達した場合は \(N\) です。
- ジャッジプログラムの都合上、標準入力の内容を必ず読み込んでください。
テストケースの生成について
V_N = 5000 です。
そのほかの V_i については、値が大きい領域と値が小さい領域ができるよう、初期値を\(0\)とし、次の処理を\(100\)回行って設定しています。
- \([1, 10]\) の整数を一様分布から選び、 \(l\) とする
- \([1, N-5-l]\) の整数を一様分布から選び、 \(p\) とする
- \([1, 200]\) の整数を一様分布から選び、 \(v\) とする
- \(V_p ... V_{p+l-1}\) に対して \(v\) を加える
とくに、 \(V_{0} = V_{N-5} = V_{N-4} = V_{N-3} = V_{N-2} = V_{N-1} = 0\) です。
入出力例
| プログラムへの入力 | プログラムの出力 | 説明 | サイコロ | マス | スコア |
|---|---|---|---|---|---|
20 6 |
スタートを除いたマスが20マスあり、サイコロを振れる回数が6であることを表します。 このサンプルは制約 \(N=500\) および \(M=5000\) を満たしていません。 |
1 2 3 4 5 6 |
0 | 0 | |
1 2 3 4 6 6 |
サイコロの目を変更します。 | 1 2 3 4 6 6 |
0 | 0 | |
6 263 6 |
サイコロの出目は \(6\) で、6番目のマスに到達し、そこに書かれている値は \(263\) です。 | 1 2 3 4 6 6 |
6 | 263 | |
1 2 3 4 6 6 |
サイコロの目は変更しません。前回と同じです。 | 1 2 3 4 6 6 |
6 | 263 | |
3 132 9 |
サイコロの出目は \(3\) で、9番目のマスに到達し、そこに書かれている値は \(132\) です。 | 1 2 3 4 6 6 |
9 | 395 | |
1 2 3 6 6 6 |
サイコロの目を変更します。 | 1 2 3 6 6 6 |
9 | 395 | |
6 0 15 |
サイコロの出目は \(6\) で、15番目のマスに到達し、そこに書かれている値は \(0\) です。 | 1 2 3 6 6 6 |
15 | 395 | |
1 2 6 6 6 6 |
サイコロの目を変更します。 | 1 2 6 6 6 6 |
15 | 395 | |
6 0 19 |
サイコロの出目は \(6\) で、ゴールで折り返して19番目のマスに到達し、そこに書かれている値は \(0\) です。 |
1 2 6 6 6 6 |
19 | 395 | |
1 2 6 6 6 3 |
サイコロの目を変更します。 | 1 2 6 6 6 3 |
19 | 395 | |
1 5000 20 |
サイコロの出目は \(1\) で、ゴールである20番目のマスに到達し、そこに書かれている値は \(5000\) です。 ゴールに到達したので、0番目のマスから再スタートとなります。 | 1 2 6 6 6 3 |
0 | 5395 | |
1 2 6 3 6 3 |
サイコロの目を変更します。 | 1 2 6 3 6 3 |
0 | 5395 | |
6 263 6 |
サイコロの出目は \(6\) で、6番目のマスに到達し、そこに書かれている値は \(263\) です。 この値は、1度目に到達した値と同じです（マスの値は変化したり消えたりしません）。 6回サイコロを振ったのでゲームは終了です。 |
1 2 6 3 6 3 |
6 | 5658 |
テスター
次のリンクから提供しています。
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
N 行 N 列のグリッドがあります。上から i 行目、左から j 列目のセルを (i, j) と表します。
各セルの上には、AからZまでのいずれかの文字が1つ書いてあるシートが1枚置かれています。
さらに、グリッドのうち、1個のセルには球状のお掃除ロボットXがいて、それ以外の P 個のセルには柱があります。
あなたは柱を移動させつつロボットを上下左右に転がして、ロボットにシートを回収させます。厳密には、あなたは最大で M 回、以下のいずれかの操作を実行できます。
- 柱を動かす: 任意の1つの柱を別のセルへ移動します。ただし、ロボットまたは柱が存在するセルを移動先として選ぶことはできません。
- ロボットを転がす: ロボットを上下左右のいずれかの方向に転がします。
- ロボットは指定された方向に転がり続けて、柱が存在するセルにぶつかると柱の直前のセルで止まります。ぶつかる柱がない場合、グリッド外に出る直前のセルで止まります。
- その後、止まったセルに文字が書いてあるシートがあれば、ロボットにそれを回収させます。ただし、一度シートを回収させたセルに再度止まった場合、シートを回収させることはできません。
全ての操作を終えた後に、ロボットに回収させた順にシートを並べて、「連続した同じ文字の長さの二乗」の和のスコアを獲得します。
（例えば、シートを A, B, B, B, A, Bの順に回収させた場合、スコアは \(1^2 + 3^2 + 1^2 + 1^2 = 12 \)です。）
うまくロボットと柱を動かすことで、スコアを最大化してください。
各テストケースの得点およびこの問題の得点は、次のように計算されます。
- 1つのテストケースでは、操作を終えた後のスコアがそのまま得点になります。
- テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
N P M
row_{0}
\(\vdots\)
row_{N-1}
sheets_{0}
\(\vdots\)
sheets_{N-1}
- N はグリッドの大きさを表す整数で、N = 40 を満たします。
- P は柱の数を表す整数で、P = 300 を満たします。
- M は問題文中で定められた操作を実行できる回数の最大値で、M = 1000 を満たします。
-
row_{i} は 長さ N の文字列で、その各文字は
o,x,-のいずれかです。row_{i} の j 番目の文字（\( 0 \leq i,j \lt N \)） が-
oなら (i,j) にロボットが存在すること -
xなら (i,j) に柱が存在すること -
-なら (i,j) にロボットも柱も存在しないこと
oは1文字、xはちょうど P 文字であることが保証されます。 -
-
sheets_{i} は 長さ N の文字列で、その各文字は
AからZのいずれかです。 sheets_{i} の j 番目の文字（\( 0 \leq i,j \lt N \)）は、(i,j) に置かれたシートに書いてある文字を表します。
出力
最大M 行出力してください。上から順に、実行する操作を出力してください。
- 柱を動かす場合、行の先頭に
Pを出力し、柱が存在するセル(r_{1}, c_{1}) と 移動先のセル(r_{2}, c_{2})を次のようにスペース区切りで出力してください（\( 0 \leq r_1, c_1, r_2, c_2 \lt N \) ）。操作前に (r_{1}, c_{1})に柱がない場合、および(r_{2}, c_{2})にロボットか柱が存在する場合、 となります。P r_1 c_1 r_2 c_2
- ロボットを転がす場合、転がす方向を表す文字を
UDLR（それぞれ上下左右に対応します）の中からひとつ出力してください。
[UDLR]
テストケースの生成について
各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータはページ下部のリンクより提供しています。
ロボットと柱の初期配置、およびシートに書いてある文字は一様乱数にしたがって生成されます。厳密にはテスターの実装を見てください。
入力例
4 2 6 ---- -o-- x--- -x-- XYZX ZAYX ZBZB XYZXこのケースは説明用のもので、入力の制約を満たしていません。
出力例
D R L P 2 0 0 1 U入出力例の説明をします。
| プログラムの出力 | 説明 | ロボットと柱の位置 | 置かれたシート | 拾ったシート |
|---|---|---|---|---|
入力で与えられた最初の状態です。ロボットは最初 (1,1)にいて、Aと書いてあるシートの上にいますが、このシートは現時点で拾えないことに注意してください。
|
---- -o-- x--- -x-- |
XYZX ZAYX ZBZB XYZX |
なし | |
D |
ロボットは (1,1) から下に移動し続け、(3,1) にある柱にぶつかり、(2,1) で止まります。そこに置かれた Bと書いてあるシートを回収させます。
|
---- ---- xo-- -x-- |
XYZX ZAYX Z ZB XYZX |
B |
R |
ロボットは (2,1) から右に移動し続け、グリッドの端である (2,3) で止まります。そこに置かれた Bと書いてあるシートを回収させます。
|
---- ---- x--o -x-- |
XYZX ZAYX Z Z XYZX |
BB |
L |
ロボットは (2,3) から左に移動し続け、(2,0) にある柱にぶつかり、(2,1) で止まります。ここでは既にシートを回収させているため、再度シートを回収させることはできません。 |
---- ---- xo-- -x-- |
XYZX ZAYX Z Z XYZX |
BB |
P 2 0 0 1 |
(2,0) に置かれた柱を、(0,1) へ移動します。 |
-x-- ---- -o-- -x-- |
XYZX ZAYX Z Z XYZX |
BB |
U |
ロボットは (2,1) から上に移動し続け、(0,1) にある柱にぶつかり、(1,1) で止まります。そこに置かれた Aと書いてあるシートを回収させます。あなたはあと1回操作をすることもできますが、途中でやめることもできます。
|
-x-- -o-- ---- -x-- |
XYZX Z YX Z Z XYZX |
BBA |
ジェネレータとテスターとサンプル入力データ
テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。