A - Circles of Inversion Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

ストーリー

魔法使いの高橋くんは、「反転の魔法陣」を使って、いくつもの目的地を決められた順に巡ろうとしている。 あらかじめ描いておいた魔法陣を一つ選び、現在位置に新たに描いた魔法陣と反応させると、選んだ魔法陣を中心として現在位置と点対称な位置へ一瞬で転移できる。 転移に使った魔法陣は消えるが、転移前の位置に描いた魔法陣は残り、次の転移に使うことができる。

高橋くんは、出発前にいくつかの魔法陣を好きな場所に描いておくことができる。 魔法陣の配置と歩行・転移の使い方を工夫し、できるだけ少ない操作ですべての目的地を順に巡る方法を考えてほしい。

小さな盤面で反転の魔法陣を使い、二つの目的地を順に訪れるアニメーション

問題文

N\times N マスの盤面がある。 左上のマスの座標を (0,0) とし、そこから下方向に i マス、右方向に j マス進んだ先のマスの座標を (i,j) とする。 魔法使いの高橋くんが盤面上を移動する。 高橋くんの初期位置 s=(s_i,s_j) と、順番に訪れる M 個の目的地 g_0,\ldots,g_{M-1} が与えられる。 あなたは、あらかじめ盤面上の好きなマスに K 個の魔法陣を描く。 高橋くんと魔法陣、または複数の魔法陣が同じマスにあってもよく、互いに移動を妨げない。

以下の操作を繰り返す。

  • 歩行：高橋くんを上下左右の隣接マスへ移す。 移動先は盤面内でなければならない。
  • 転移：魔法陣が存在するマスを一つ選び、高橋くんの現在位置に新たな魔法陣を描く。 高橋くんは、選んだマスを中心として現在位置と点対称な位置へ転移する。 すなわち、操作前の高橋くんの位置を (i,j)、選んだマスの座標を (a,b) として、高橋くんを (2a-i,2b-j) へ移す。 選んだマスの魔法陣を一つ消し、出発地点 (i,j) に描いた新たな魔法陣を残す。 転移先が盤面内にある場合だけ実行できる。 他の魔法陣は変化しない。

初期位置からすべての目的地を指定順に歩行のみで訪れるために必要な最小の操作回数を T とする。 すなわち、T は初期位置から最初の目的地まで、および隣り合う目的地間のマンハッタン距離の総和である。 操作は合計で最大 T 回まで行うことができる。

各操作の直後、高橋くんが次の目的地にいれば、その目的地を訪れたものとする。 次に訪れるべき目的地以外に到着しても、訪れた目的地の数は増えない。 後で訪れる予定の目的地に先に到着した場合も、その目的地の順番が来たら改めて訪れる必要がある。 魔法陣の初期配置と操作列を決め、できるだけ短い操作列ですべての目的地を指定順に訪れよ。

得点

出力した操作列の長さを A、指定順に訪れた目的地の数を V とする。 このとき、以下の得点が得られる。

\[ \begin{cases} M+T-A+1 & (V=M) \\ V+1 & (V<M) \end{cases} \]

合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となり、提出の得点は 0 点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。

入力

入力は以下の形式で標準入力から与えられる。

N M K T
s_i s_j
g_{0,i} g_{0,j}
\vdots
g_{M-1,i} g_{M-1,j}

ここで g_r=(g_{r,i},g_{r,j}) は r 番目の目的地である。 各値は以下の制約を満たす。

  • N=128
  • M=150
  • K=3
  • T は前述の歩行のみで全目的地を訪れるための最小操作回数である。
  • すべての座標の成分は 0 以上 N 未満の整数である。
  • s,g_0,\ldots,g_{M-1} はすべて異なる。

出力

以下の形式で標準出力に出力せよ。

a_0 b_0
\vdots
a_{K-1} b_{K-1}
\mathrm{op}_0
\vdots
\mathrm{op}_{A-1}

最初の K 行には、あらかじめ描く K 個の魔法陣の座標 (a_k,b_k) を任意の順序で出力せよ。 各座標の成分は 0 以上 N 未満の整数でなければならない。 続いて操作を 1 行に一つずつ、以下の形式で出力せよ。

  • 上下左右への歩行：それぞれ U、D、L、R
  • マス (a,b) の魔法陣を使う転移：J a b

転移で指定する座標は 0\leq a,b<N を満たし、マス (a,b) には魔法陣が存在しなければならない。 操作回数は T 以下とし、盤外へ移動する操作を含めてはならない。

例を見る

入力生成方法

N^2 個のマスから相異なる M+1 個を順序付きで一様に選び、先頭を s、残りを順に g_0,\ldots,g_{M-1} とする。 T は選ばれた初期位置と目的地から計算する。

ツール(入力ジェネレータ・ビジュアライザ)

  • Web版: ローカル版より高性能でアニメーション表示が可能です。
  • ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。 コンパイルが通らない場合は rustup update をお試し下さい。

コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。 ご注意下さい。

Story

Takahashi the wizard wants to visit several destinations in a specified order using "circles of inversion." By choosing a magic circle drawn in advance and making it react with a new circle drawn at his current position, he can instantly teleport to the point symmetric to his current position about the chosen circle. The circle used for teleportation disappears, but the new circle at his position before teleportation remains and can be used for another teleportation.

Before setting out, Takahashi can draw several magic circles wherever he likes. Help him choose their positions and combine walking and teleportation to visit all the destinations in order with as few operations as possible.

An animation of visiting two destinations in order using circles of inversion on a small grid

Problem Statement

There is an N\times N grid. Let (0,0) be the coordinates of the top-left cell, and let (i,j) be the coordinates of the cell located i cells downward and j cells to the right from there. Takahashi the wizard moves on this grid. You are given his initial position s=(s_i,s_j) and M destinations g_0,\ldots,g_{M-1} to visit in order. You first draw K magic circles in cells of your choice on the grid. Takahashi and magic circles, or multiple magic circles, may occupy the same cell and do not obstruct each other.

Repeat the following operations.

  • Walk: Move Takahashi to an adjacent cell up, down, left, or right. The destination cell must be inside the grid.
  • Teleport: Choose a cell containing a magic circle, then draw a new magic circle at Takahashi's current position. Takahashi teleports to the point symmetric to his current position about the chosen cell. That is, if his position before the operation is (i,j) and the chosen cell is (a,b), move him to (2a-i,2b-j). Remove one magic circle from the chosen cell, leaving the new circle drawn at the departure point (i,j). This operation is allowed only if the destination cell is inside the grid. All other magic circles remain unchanged.

Let T be the minimum number of operations needed to visit all destinations in the specified order from the initial position using only walking. In other words, T is the sum of the Manhattan distance from the initial position to the first destination and the Manhattan distances between consecutive destinations. You may perform at most T operations in total.

Immediately after each operation, if Takahashi is at the next destination, it is counted as visited. Arriving at any other destination does not increase the number of visited destinations. Even if he reaches a later destination early, he must visit it again when its turn comes. Choose the initial positions of the magic circles and a sequence of operations to visit all destinations in the specified order with as few operations as possible.

Scoring

Let A be the length of the output operation sequence and V be the number of destinations visited in the specified order. Your score is calculated as follows.

\[ \begin{cases} M+T-A+1 & (V=M) \\ V+1 & (V<M) \end{cases} \]

There are 150 test cases, and the score of a submission is the sum of the scores for all test cases. 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 K T
s_i s_j
g_{0,i} g_{0,j}
\vdots
g_{M-1,i} g_{M-1,j}

Here, g_r=(g_{r,i},g_{r,j}) is the r-th destination. Each value satisfies the following constraints.

  • N=128
  • M=150
  • K=3
  • T is the minimum number of operations needed to visit all destinations using only walking, as defined above.
  • All coordinate components are integers between 0 and N-1, inclusive.
  • s,g_0,\ldots,g_{M-1} are all distinct.

Output

Output to Standard Output in the following format.

a_0 b_0
\vdots
a_{K-1} b_{K-1}
\mathrm{op}_0
\vdots
\mathrm{op}_{A-1}

In the first K lines, output the coordinates (a_k,b_k) of the K magic circles drawn in advance, in any order. Each coordinate component must be an integer between 0 and N-1, inclusive. Then output one operation per line in the following format.

  • Walk up, down, left, or right: U, D, L, or R, respectively.
  • Teleport using a magic circle at (a,b): J a b

The coordinates specified for teleportation must satisfy 0\leq a,b<N, and cell (a,b) must contain a magic circle. The number of operations must be at most T, and no operation may move Takahashi outside the grid.

Show example

Input Generation

Choose an ordered sequence of M+1 distinct cells uniformly at random from the N^2 cells, and use the first cell as s and the remaining cells as g_0,\ldots,g_{M-1} in order. Compute T from the chosen initial position and destinations.

Tools (Input generator and visualizer)

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.