A - Ward the Village 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

ストーリー

あなたは日本の山奥にある村の村長で、毎年お盆になると発生する怪異に頭を悩ませていた。 今年は巫女の占いにより、村中で 10000 回の怪異が起こることが分かった。 そこで、怪異の起こる場所のできるだけ近くに魔除けのお札を立て、被害を抑えることにした。 占いは怪異の起こる場所と順番を告げるが、猶予はない。 あなたは村外れの社を出て村を巡り、怪異の発生と並行してお札を立てていかねばならない。 お札は、社または直前に立てたお札から神力を受け継いで初めて魔除けの力を持つ。 神力の通り道は巫女の祈祷で 3 通りまで開くことができ、どの位置関係に開くかは、社を出る前にあなたが決める。 村が受ける被害をできるだけ小さく抑えてほしい。

問題文

村は N\times N マスに区切られている。 左上のマスの座標を (0,0) とし、そこから下方向に i マス、右方向に j マス進んだ先のマスの座標を (i,j) とする。 各ターン t=0,1,\cdots,N^2-1 に怪異が発生するマスの座標 (a_t,b_t) が、あらかじめ入力として与えられる。

まず、神力の通り道となる M 個の位置関係 (i_0,j_0),\cdots,(i_{M-1},j_{M-1}) を自由に定める。 ただし、0 以上 M 未満のすべての m について、i_m と j_m は 0 以上 N 未満の整数でなければならない。

初期状態では、危険度は 0、あなたの位置 P は社のあるマス (0,0) であり、お札は 1 枚も立っていない。 この状態から、以下の操作を t=0,1,\cdots,N^2-1 の順に行う。

  1. 0 以上 M 未満の整数 m_t を選ぶ。
  2. あなたは P から下方向に i_{m_t} マス、右方向に j_{m_t} マス移動する。盤面の上下と左右はループしており、移動前の P が (i,j) のとき、移動後の P は ((i+i_{m_t})\bmod N,\ (j+j_{m_t})\bmod N) となる。
  3. 移動後の P のマスにお札を立てる。既にお札が立っているマスに重ねて立てても構わない。一度立てたお札は最後のターンまで残り続ける。
  4. マス (a_t,b_t) に怪異が発生し、危険度に \mathrm{floor}(d_t\times\sqrt{t+1}) が加算される。ここで d_t は、マス (a_t,b_t) とお札が立っているマスとのマンハッタン距離の最小値である。

マス (i,j) とマス (i',j') のマンハッタン距離は |i-i'|+|j-j'| である。 あなたの移動とは異なり、この距離の計算では盤面の上下と左右はループしないことに注意せよ。 操作 4 の時点では必ず 1 枚以上のお札が立っているため、d_t は常に定まる。 また、(a_t,b_t) にお札が立っている場合は d_t=0 となり、危険度は増えない。

全 N^2 ターンが終了した時点での危険度をできるだけ小さくせよ。

例

説明のため、N=5, M=3 とし、最初の 3 ターンだけを考える。 位置関係を (i_0,j_0)=(0,1)、(i_1,j_1)=(1,0)、(i_2,j_2)=(3,4) と定め、m_0=0, m_1=1, m_2=2 を選ぶ。 下図では、星が立てたお札、赤い印が怪異の発生するマス、青い丸と矢印があなたの位置と移動を表す。

t = 0 m₀ = 0, +(0, 1) mod 5 d₀ = 2, +2 01234 01234 P: (0, 0) → (0, 1) t = 1 m₁ = 1, +(1, 0) mod 5 d₁ = 3, +4 01234 01234 P: (0, 1) → (1, 1) t = 2 m₂ = 2, +(3, 4) mod 5 d₂ = 0, +0 01234 01234 P: (1, 1) → (4, 0)

t=0 では、(0,0) から (0,1) へ移動してお札を立てる。 怪異は (0,3) に発生するため d_0=2 であり、危険度に \mathrm{floor}(2\sqrt{1})=2 が加算される。 t=1 では (1,1) へ移動し、怪異は (0,4) に発生する。 怪異が発生したマスから、直前のターンに (0,1) へ立てたお札までの距離は 3、このターンに (1,1) へ立てたお札までの距離は 4 である。 したがって d_1=3 であり、危険度に \mathrm{floor}(3\sqrt{2})=4 が加算される。 t=2 では、盤面がループしているため、(1,1) から下に 3 マス、右に 4 マス移動した先は (4,0) となる。 このマスにお札を立てた直後に同じマスで怪異が発生するため d_2=0 であり、危険度は増えない。 したがって、3 ターン終了時点での危険度は 2+4+0=6 となる。

得点

全 N^2 ターンが終了した時点での危険度を D とする。 このとき、以下の得点が得られる。

\[ \mathrm{round}\left(\frac{10^6\times N^3}{D+1}\right) \]

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

入力

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

N M
a_0 b_0
a_1 b_1
\vdots
a_{N^2-1} b_{N^2-1}

各値は以下の制約を満たす。

  • N=100
  • M=3
  • 0\leq a_t<N、0\leq b_t<N
  • (a_0,b_0),\cdots,(a_{N^2-1},b_{N^2-1}) は互いに異なる

出力

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

i_0 j_0
i_1 j_1
\vdots
i_{M-1} j_{M-1}
m_0
m_1
\vdots
m_{N^2-1}

例を見る

入力生成方法

N=100 と M=3 は固定である。 (a_0,b_0),\cdots,(a_{N^2-1},b_{N^2-1}) は、盤面の N^2 個のマスの座標全体を一様ランダムに並べ替えたものである。

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

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

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

今回の短期コンテストから、生成AIの利用が一部の例外を除き、禁止となります。詳細はこちらの記事をご確認ください。

Story

You are the chief of a village deep in the mountains of Japan, and the hauntings that break out every year during the Obon season have long troubled you. This year, a divination by the shrine maiden has revealed that 10000 hauntings will occur throughout the village. You therefore decided to set up protective talismans as close as possible to where the hauntings occur, so as to limit the damage. The divination tells you where the hauntings occur and in what order, but it grants you no time to prepare. You must leave the shrine on the outskirts of the village and travel around, setting up talismans while the hauntings are already taking place. A talisman wards off the hauntings with the divine power it inherits from the shrine or the talisman set up immediately before it. The shrine maiden's prayer can open at most 3 paths for the divine power, and you choose the positional relationships they run along before you leave the shrine. Please keep the damage to the village as small as you can.

Problem Statement

The village is divided into an N\times N grid of cells. 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. The coordinates (a_t,b_t) of the cell where a haunting occurs on each turn t=0,1,\cdots,N^2-1 are given as input in advance.

First, you freely choose M positional relationships (i_0,j_0),\cdots,(i_{M-1},j_{M-1}) along which the divine power may run. Here, for every m with 0\leq m<M, i_m and j_m must be integers satisfying 0\leq i_m<N and 0\leq j_m<N.

Initially, the danger level is 0, your position P is the cell (0,0) where the shrine stands, and no talisman has been set up. Starting from this state, you perform the following operation for t=0,1,\cdots,N^2-1.

  1. Choose an integer m_t with 0\leq m_t<M.
  2. You move i_{m_t} cells downward and j_{m_t} cells to the right from P. The grid wraps around both vertically and horizontally, so if P is (i,j) before the move, then P becomes ((i+i_{m_t})\bmod N,\ (j+j_{m_t})\bmod N) after the move.
  3. You set up a talisman on the cell P after the move. You may set one up on a cell that already has one. Once set up, a talisman remains until the final turn.
  4. A haunting occurs on the cell (a_t,b_t), and \mathrm{floor}(d_t\times\sqrt{t+1}) is added to the danger level. Here, d_t is the minimum Manhattan distance between the cell (a_t,b_t) and a cell with a talisman on it.

The Manhattan distance between the cells (i,j) and (i',j') is |i-i'|+|j-j'|. Note that, unlike your move, the grid does not wrap around when this distance is computed. d_t is always well-defined, since at least one talisman has been set up by the time operation 4 takes place. Note also that when a talisman stands on (a_t,b_t) d_t=0, in which case the danger level does not increase.

Minimize the danger level after all N^2 turns have finished.

Example

For illustration, let N=5 and M=3, and consider only the first three turns. Choose (i_0,j_0)=(0,1), (i_1,j_1)=(1,0), and (i_2,j_2)=(3,4) as the positional relationships, and choose m_0=0, m_1=1, and m_2=2. In the figure below, stars indicate talismans, red crosses indicate cells where hauntings occur, and blue circles and arrows indicate your positions and moves.

t = 0 m₀ = 0, +(0, 1) mod 5 d₀ = 2, +2 01234 01234 P: (0, 0) → (0, 1) t = 1 m₁ = 1, +(1, 0) mod 5 d₁ = 3, +4 01234 01234 P: (0, 1) → (1, 1) t = 2 m₂ = 2, +(3, 4) mod 5 d₂ = 0, +0 01234 01234 P: (1, 1) → (4, 0)

At t=0, you move from (0,0) to (0,1) and set up a talisman. The haunting occurs at (0,3), so d_0=2 and \mathrm{floor}(2\sqrt{1})=2 is added to the danger level. At t=1, you move to (1,1), and the haunting occurs at (0,4). The distances from this cell to the talisman set up at (0,1) on the previous turn and the one set up at (1,1) on this turn are 3 and 4, respectively. Thus, d_1=3 and \mathrm{floor}(3\sqrt{2})=4 is added to the danger level. At t=2, since the grid wraps around, moving three cells downward and four cells to the right from (1,1) takes you to (4,0). The haunting occurs on this cell immediately after you set up a talisman there, so d_2=0 and the danger level does not increase. Thus, the danger level after the three turns is 2+4+0=6.

Scoring

Let D be the danger level after all N^2 turns have finished. You then obtain the following score.

\[ \mathrm{round}\left(\frac{10^6\times N^3}{D+1}\right) \]

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
a_0 b_0
a_1 b_1
\vdots
a_{N^2-1} b_{N^2-1}

Each value satisfies the following constraints.

  • N=100
  • M=3
  • 0\leq a_t<N, 0\leq b_t<N
  • (a_0,b_0),\cdots,(a_{N^2-1},b_{N^2-1}) are pairwise distinct

Output

Output to Standard Output in the following format.

i_0 j_0
i_1 j_1
\vdots
i_{M-1} j_{M-1}
m_0
m_1
\vdots
m_{N^2-1}

Show example

Input Generation

N=100 and M=3 are fixed. (a_0,b_0),\cdots,(a_{N^2-1},b_{N^2-1}) is a uniformly random permutation of the coordinates of all N^2 cells of the grid.

Tools (Input generator and visualizer)

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

Starting with this short contest, the use of generative AI will be prohibited, with limited exceptions. Please refer to this post for further details.