I - Collecting Gems is Fun

Time Limit: 2 sec / Memory Limit: 512 MB

配点:1500

問題文

ある夏の暑い日, E869120 は, AtCoder 公園に行った.
公園は, HW 列のグリッドで表される. 左上のマスは (1, 1), 右下のマスは (H, W) である.
また, この公園には N 個の宝石が落ちている. 同じマスに 2 個以上の宝石が落ちていることはない.

さて, 彼は公園にある宝石を全て集めようと思った.
彼は特別な嗅覚を持っており, 自分で事前に設定した「相対的な位置」に宝石が 1 つ以上あれば, 「宝石は近い位置にある」という情報が分かる.
ただし, 相対的な位置の例は, 以下のようなものである.

上の左から 1 番目の図において, E869120 が今マス (4, 4) にいる場合, マス (6, 5)(2, 4) にある場合は近いと判定される. なぜなら, 自分を (0, 0) として見たときにそれぞれの座標は (2, 1)(-2, 0) となり, これらは近いから.
しかし, マス (2, 3) にある宝石は「近い」と判定されない. なぜなら, 相対的に (-2, -1) は近いマスに含まれないから.

さて, 彼は最初マス (1, 1) にいる. 「近い宝石が 1 個以上ある」「そうでない」だけの情報で, 全ての宝石をできるだけ短い時間で集める方法を書いたプログラムを書け.
ただし, 彼は 1 マス {左, 右, 下, 上} のどれかの方向に移動するのに 1 秒かかり, 自分の今いるマスに宝石がある場合 0 秒で掘ることができると仮定してよい.

入出力

この問題はインタラクティブ問題 (プログラムの入力と出力でジャッジとコミュニケーションをとる問題) であり, 入出力の形式が特殊である.

まず, あなたは公園の縦の長さ H, 横の長さ W, 宝石の個数 N を以下のような形式で受け取る.

H W N

次に, あなたは「近いに含まれる相対的な位置」を設定しなければならない. 以下の形式で設定すること.

P
x_1 y_1
x_2 y_2
...
x_P y_P

1 行目に, 近いに含まれる相対的な位置の個数 P を出力しなければならない. 0 \leq P \leq 500 でなければならない.
2 行目から P 行にわたって, 相対的な位置 (x_i, y_i) を出力しなければならない. また, x_i,y_i の値の絶対値は 10^9 以下である必要がある. ただし, 自分のマスに宝石がある場合すぐに取ってしまうので, (x_i, y_i) \neq (0, 0) でなければならない.

次に, (☆) -> (★) -> (☆) -> (★) -> ... の順に以下のように処理を繰り返す.

(☆) コンピューターがあなたに情報を与える. 情報は以下のような形式で与えられる.

S

情報は以下のように分類される.

  • far: このマスに宝石はなく, かつあなたが設定した「近い位置」にも宝石はない.
  • close: このマスに宝石はないが, あなたが設定した「近い位置」に宝石はある.
  • get-far: このマスに宝石はあったので E869120 は宝石を取り, その後の状態で「近い位置」に宝石がない.
  • get-close: このマスに宝石はあったので E869120 は宝石を取り, その後の状態で「近い位置」に宝石がある.
  • get-clear: このマスに宝石があったので E869120 は宝石を取り, それで宝石が全て取られたときに必ず出力される. これを受け取ったらすぐにプログラムを終了させること.

(★) E869120 が移動する. 以下のような形式で移動の方向を出力すること.

c

cL のとき左に 1 マス, R のとき右に 1 マス, U のとき上に 1 マス, D のとき下に 1 マス動くことを意味する.
また, 公園の外に出るような移動はしてはならない.


注意

出力形式を間違えたり公園の外に出るような移動をした場合の結果は不定である. (WA になるとは限らない)
また, 出力の最後に flush しなければならず, そうしない場合 TLE となることがある.
E869120 は, 10 \ 000 回までしか移動をしてはならない.

制約

  • H = 100
  • W = 100
  • N = 200
  • 公園の中にある宝石は, 10000 個のマスからランダムに 200 個選ぶという方法で位置が決められている.

得点

この問題には 15 個テストケースがある. 1 個あたり 100 点で採点される.
移動した回数を L とおくとき, 各ケースの得点は, 以下のように定まる.

  • L \leq 2 \ 100 のとき, 100 点.
  • 2 \ 101 \leq L \leq 2 \ 260 のとき, floor(100 - \frac{L - 2100}{8}) 点.
  • 2 \ 261 \leq L \leq 2 \ 540 のとき, floor(80 - \frac{L - 2260}{14}) 点.
  • 2 \ 541 \leq L \leq 3 \ 000 のとき, floor(60 - \frac{L - 2540}{25}) 点.
  • 3 \ 001 \leq L \leq 5 \ 000 のとき, floor(41.6 - \frac{L - 3000}{125}) 点.
  • 5 \ 001 \leq L \leq 6 \ 000 のとき, 24 点.
  • 6 \ 001 \leq L \leq 7 \ 000 のとき, 21 点.
  • 7 \ 001 \leq L \leq 8 \ 000 のとき, 18 点.
  • 8 \ 001 \leq L \leq 9 \ 000 のとき, 15 点.
  • 9 \ 001 \leq L \leq 10 \ 000 のとき, 3 点.

移動回数と得点の関係を表したグラフは, 以下のようになる.

入出力例

以下の図は, この入出力例での公園の状態・「近い位置」の選び方(つまり, ここでは 8 近傍)を表している.

例えば, 以下のようなやり取りが行われる.

入力 出力 備考
4 4 4 H, W, N の値を入力.
8
-1 -1
-1 0
-1 1
0 -1
0 1
1 -1
1 0
1 1
「近い位置」に含まれる方向を入力.
get-far 今 (1, 1) にいるので, 宝石が取れる.
R (1, 2) に動く.
close マス (2, 3) にある宝石が「近い」.
D (2, 2) に動く.
close マス (2, 3), (3, 2) にある宝石が「近い」.
D (3, 2) に動く.
get-close (3, 2) の宝石を取った. マス (2, 3) にある宝石が「近い」.
R (3, 3) に動く.
close マス (2, 3), (2, 4) にある宝石が「近い」.
U (2, 3) に動く.
get-close マス (2, 3) にある宝石を取る. マス (2, 4) にある宝石が「近い」.
U (2, 4) に動く.
get-clear マス (2, 4) にある宝石を取る. これで全ての宝石が取れた.

Max Score: 1500 points

Problem Statement

One day, E869120 the Coder went to "AtCoder Natural Park".
The park represented as H*W grid. The top-left corner cell is (1,1) and the bottom-right corner cell is (H,W).
In addition, N gems drop in the park. In each cell, there are no more than 1 gem drops.

He want to collect all gems in the park.
He have "special smell-sense", so if there are 1 or more gems in relative-position that he decide beforehand, he think that "there is a gem near me".
The example of "relative position" is as follows:

In the left picture, if E869120 exists in the cell (4, 4), gems in cell (6, 5) and (2, 4) is "near". Suppose his relative position is (0, 0). In this case, the relative position of gem in example is (2, 1) and (-2, 0) in order. To see the picture, both (2, 1) and (-2, 0) is near.
But (2, 3) isn't near because its relative position is (-2, -1) and it is not near as long as see the picture.

However, he can move to one of 4-adjacent cells which share a side in 1 second. If there is a gem on the cell that E869120 exists, he pick it automatically in 0 second.
Initially, he is on the cell (1, 1). Please write the program that collect all gems in the park as fast as possible.

Input and Output

This problem is "interactive task" (the task which has to take communications with input and output of program), so the format of input/output is special.

First, you are given the size of "AtCoder Natural Park": H and W. You are also given the number of gems: N. The input format is as follows:

H W N

Second, you must set the relative-direction which includes "near", to make E869120's "special smell-sense".

P
x_1 y_1
x_2 y_2
...
x_P y_P

In the 1-st line, you should output the number of relative-position which include "near": P. 0 \leq P \leq 500 should be satisfied.
From the 2-nd line to P+1-th line, you should output relative-position: (x_i, y_i). x_i,y_i should be greater than -10^9 and less than 10^9. If there is gem on the cell that E869120 exists, he pick it instantly. So, (x_i, y_i) should not be (0, 0).

Next, it repeats the following two processes (☆) and (★) alternately (the first process is (☆)).

(☆) You are given an information as follows:

S

The information is classified as follows:

  • far: There is no gems in his cells. In addition, there is no gem in relative-position that you set.
  • close: There is no gems in his cells. In addition, there is 1 or more gems in relative-position that you set.
  • get-far: There is a gem in his cells, so E869120 picks it. In addition, there is no gem in relative-position that you set after he picks.
  • get-close: There is a gem in his cells, so E869120 picks it. In addition, there is 1 or more gems in relative-position that you set after he picks.
  • get-clear: There is a gem in his cells, so E869120 picks it. In addition, all gems collected. You have to terminate your program if you program is given get-clear.

(★) E869120 moves. You should print as follows:

c
  • If c is L, it means he moves to the left cell.
  • If c is R, it means he moves to the right cell.
  • If c is U, it means he moves to the up cell.
  • If c is D, it means he moves to the down cell.
  • He should not move to outside of the park.

Note

If your output format is invalid or he moves outside of the park, the verdict is undefined. (it means it does not necessarily get WA)
And also, you must flush Standard Output. E869120 should not move more than 10 \ 000 times.

Constraints

  • H = 100
  • W = 100
  • N = 200
  • Test case is generated randomly.

Scoring

There are 15 testcases in this problem. For each cases, the max score is 100 points.
Let L be the number of moves. The point is calculated as follows:

  • If L \leq 2 \ 100, 100 points.
  • If 2 \ 101 \leq L \leq 2 \ 260, floor(100 - \frac{L - 2100}{8}) points.
  • If 2 \ 261 \leq L \leq 2 \ 540, floor(80 - \frac{L - 2260}{14}) points.
  • If 2 \ 541 \leq L \leq 3 \ 000, floor(60 - \frac{L - 2540}{25}) points.
  • If 3 \ 001 \leq L \leq 5 \ 000, floor(41.6 - \frac{L - 3000}{125}) points.
  • If 5 \ 001 \leq L \leq 6 \ 000, 24 points.
  • If 6 \ 001 \leq L \leq 7 \ 000, 21 points.
  • If 7 \ 001 \leq L \leq 8 \ 000, 18 points.
  • If 8 \ 001 \leq L \leq 9 \ 000, 15 points.
  • If 9 \ 001 \leq L \leq 10 \ 000, 3 points.

The graph that represents the correlation between the number of moves and score is as follows:

Sample Input and Output

The state of the park and the relative direction that includes "near" is as follows:

The interaction between computer and judge is as follows:

Input Output Message
4 4 4 Input the value of H, W, N.
8
-1 -1
-1 0
-1 1
0 -1
0 1
1 -1
1 0
1 1
Input relative directions.
get-far Currently he is (1, 1). Get a gem.
R Move to (1, 2).
close A gem in (2, 3) is near.
D Move to (2, 2).
close Gems in (2, 3) and (3, 2) is near.
D Move to (3, 2).
get-close Get a gem in (3, 2). A gem in (2, 3) is still near.
R Move to (3, 3).
close Gems in (2, 3) and (2, 4) is near.
U Move to (2, 3).
get-close Get a gem in (2, 3). A gem in (2, 4) is still near.
U Move to (2, 4).
get-clear Get a gem in (2, 4). All gems collected.