AT_ahc057_a [AHC057A] Molecules

AtCoder研究所では、新しい分子の開発を行っている。 天才化学者である髙橋くんは、動き回る原子同士を好きなタイミングで結合させて、分子を作ることができる。 ただし、原子を結合するには距離に応じてエネルギーを消費してしまうので、できるだけ少ないエネルギーで決められた数の分子を作りたい。

$ 0 \leq x < L = 10^5 $ 、 $ 0 \leq y < L = 10^5 $ からなる2次元平面を考える。ただし、この平面は左右端（ $ x = 0 $ と $ x = L $ ）、および上下端（ $ y = 0 $ と $ y = L $ ）がそれぞれつながっており、全体として[トーラス](https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%BC%E3%83%A9%E3%82%B9)構造となっている。範囲外の座標は、 $ x $ および $ y $ をそれぞれ $ L $ で割った余りに置き換えることで、常に $ 0 \leq x, y < L $ の範囲に正規化される。例えば、位置 $ (10000, 90000) $ から $ (-20000, 30000) $ 進んだ先の座標は $ (90000, 20000) $ である。 この平面上に $ N $ 個の点が存在する。 $ t = 0 $ において、 $ i $ 番目の点（ $ 0 \leq i < N $ ）の初期位置 $ (x_i, y_i) $ （ $ 0 \leq x_i, y_i < L $ ）と初期速度 $ (vx_i, vy_i) $ （ $ -100 \leq vx_i, vy_i \leq 100 $ ）が入力で与えられる。初期状態では、各点は独立した連結成分を形成している。 各時刻 $ t = 0, 1, \ldots, T - 1 $ において、以下の **1. 結合フェーズ** と **2. 移動フェーズ** の順で交互に処理を行う。 **1. 結合フェーズ** 時刻 $ t $ において、異なる連結成分に属する 2 つの点を **結合** することができる。同一時刻に複数の結合を行ってもよい。 点 $ i $ の時刻 $ t $ における位置を $ (x_i, y_i) $ 、点 $ j $ の時刻 $ t $ における位置を $ (x_j, y_j) $ としたとき、点 $ i $ と点 $ j $ を結合する際の **結合コスト** $ D $ は、以下の距離の式で計算される： \\\[ D = \\mathrm{round}\\left( \\sqrt{ \\bigl(\\min(L - \\Delta x,\\ \\Delta x)\\bigr)^2 + \\bigl(\\min(L - \\Delta y,\\ \\Delta y)\\bigr)^2 } \\right) \\\] \\\[ \\Delta x = |x\_i - x\_j|,\\quad \\Delta y = |y\_i - y\_j| \\\] 点を結合すると、運動量保存則に従って連結成分の速度が更新される。結合前の時点において、点 $ i $ が速度 $ (vx_A, vy_A) $ で動く連結成分 $ A $ に属し、点 $ j $ が速度 $ (vx_B, vy_B) $ で動く連結成分 $ B $ に属しているとする。連結成分 $ A $ および連結成分 $ B $ に属しているすべての点について、結合後の連結成分の速度 $ (vx_{\text{new}}, vy_{\text{new}}) $ は以下のように更新される： \\\[ (vx\_{\\text{new}}, vy\_{\\text{new}}) = \\left( \\frac{|A| \\times vx\_A + |B| \\times vx\_B}{|A| + |B|}, \\frac{|A| \\times vy\_A + |B| \\times vy\_B}{|A| + |B|} \\right) \\\] ここで、 $ |A| $ 、 $ |B| $ はそれぞれ連結成分に含まれる点の数を示す。結合後、その連結成分に属するすべての点は、**同じ速度**で動くようになる。結合によって点の位置は変化しない。また、同一時刻内での結合の順序は、結合後の位置、結合コスト、および連結成分の速度に影響しない。 座標および速度は小数となることがあるが、計算はすべて倍精度浮動小数（double）で管理される。 **2. 移動フェーズ** 各連結成分に属するすべての点の位置を同時に更新する。点 $ i $ の時刻 $ t $ における位置を $ (x_i, y_i) $ 、点 $ i $ が属する連結成分の速度を $ (vx_i, vy_i) $ とすると、時刻 $ t + 1 $ における点 $ i $ の位置 $ (x_i', y_i') $ は以下のようになる： \\\[ (x\_i', y\_i') = ((x\_i + vx\_i) \\bmod L, (y\_i + vy\_i) \\bmod L) \\\] 時刻 $ T $ において、連結成分数が **ちょうど $ M $ 個**、かつ各連結成分のサイズが **ちょうど $ K $** となるように結合を計画し、**結合コスト $ D $ の合計**を最小化せよ。 #### 結合と移動の例 >  > > 上図では、3 つの点を 1 つの連結成分にまとめる例を示している。 まず最初に、左下と右下の 2 点を結合し、進行方向が上向きに変化する。 次に、上部を右向きに進む点と結合し、進行方向は右上に変化する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ T $ $ M $ $ K $ $ L $ $ x_0 $ $ y_0 $ $ vx_0 $ $ vy_0 $ $ x_1 $ $ y_1 $ $ vx_1 $ $ vy_1 $ $ \vdots $ $ x_{N-1} $ $ y_{N-1} $ $ vx_{N-1} $ $ vy_{N-1} $ - 点の総数は $ N = 300 $ である。 - 総ステップ数は $ T = 1000 $ である。 - 目標連結成分数は $ M = 10 $ である。 - 各連結成分の目標サイズは $ K = 30 $ である。 - 空間の一辺の長さは $ L = 10^5 $ である。 - $ (x_i, y_i) $ は点 $ i $ の初期位置を表し、 $ 0 \leq x_i, y_i < L $ を満たす整数値である。 - $ (vx_i, vy_i) $ は点 $ i $ の初期速度を表し、 $ -100 \leq vx_i, vy_i \leq 100 $ を満たす整数値である。

ちょうど $ N - M $ 行を標準出力に出力せよ。各行は以下の 3 つの整数からなり、時刻 $ t $ に点 $ i $ と点 $ j $ を結合することを表す。 出力の順番は任意であるが、処理は時刻 $ t $ の昇順で行われる。 > $ t $ $ i $ $ j $ 出力は以下の条件を満たさなければならない。 - $ 0 \leq t < T $ - $ 0 \leq i, j < N $ 、かつ $ i \neq j $ であること [例を見る](https://img.atcoder.jp/ahc057/BJTm8xSg.html?lang=ja&seed=0&output=sample)

### 得点 すべての結合コスト $ D $ の合計を $ D_{\text{sum}} $ とする。このとき、1 テストケースの得点は以下のように計算される。得点は大きいほど良い。 \\\[ \\mathrm{Score} = \\mathrm{round}\\!\\left(10^{6} \\times \\log\_{2}\\!\\left( \\frac{L \\times (N - M)}{D\_{\\text{sum}} + 1} \\right)\\right) \\\] 以下の場合、WA となる。 - 無効な出力を行った場合 - 時刻 $ T $ 時点で連結成分数が **ちょうど $ M $ 個**、各連結成分のサイズが **ちょうど $ K $** でない場合 - すでに同一連結成分に属している点の間で結合が指定された場合 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ \mathrm{rand}(L,U) $ : $ L $ 以上 $ U $ 以下の整数値を一様ランダムに生成する。 **初期位置の生成** 各点 $ i $ ごとに独立に、 $ x_i = \mathrm{rand}(0, L - 1) $ 、 $ y_i = \mathrm{rand}(0, L - 1) $ により生成する。 **初期速度の生成** 各点 $ i $ ごとに独立に、 $ vx_i = \mathrm{rand}(-100, 100) $ 、 $ vy_i = \mathrm{rand}(-100, 100) $ により生成する。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc057/BJTm8xSg.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc057/BJTm8xSg.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc057/BJTm8xSg_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。