/ 
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
この世界は 3 次元、すなわち位置を座標で示すためには (x, y, z) と 3 つの数が必要です。今回はそれよりも高次元の 200 次元の世界について考えてみましょう。つまり、ある点の座標は (x_1, x_2, ..., x_{200}) と 200 個の数で表現されるということです。
いま、200 次元空間上に 1 から 5,000 までの異なる番号がつけられた点が 5,000 個あります。これら 5,000 個の点に対して、次の条件を満たすように点どうしを結ぶことを考えます。
- どの点からどの別の点に対しても、結ばれた点への移動を繰り返すことで到達することができる。
- その移動の際に同じ点を 2 回以上通らないことにすると、移動方法が 1 通りに定まる。
別の言葉でいえば、点たちが木になるように結びたいということです。
そして、コンテストの問題としてお約束っぽいですが、できるだけコストが小さくなるように結ぶことを考えましょう。ここで、2 つの点 (a_1, a_2, ..., a_{200}) と (b_1, b_2, ..., b_{200}) を結ぶコストは次のようにして定まります。
-
2 つの点の
類似度
を次の式で定めます。（これは「コサイン類似度」と呼ばれているものです）
- このとき、2 つの点を結ぶコストは 1 - 類似度 となります。つまり、類似度が高いほどコストが低く、類似度が低いほどコストが高くなります。
全体のコストは、点を結ぶのに要したコストの和で決まります。このとき、できるだけコストが小さくなるように結ぶ方法を求めるプログラムを作成してください。ただし、コストを最小にする必要はなく、出力した結び方のコストが 最小なものの 1.01 倍以内のコストに収まっていれば Accept とします。
入力
入力は以下の形式で標準入力から与えられる。
seed
- 1 行目には整数 seed (1 ≦ seed ≦ 10^6) が与えられる。
実際の点の座標は、初期化に seed を用いた擬似乱数によって生成する。すべての点の座標の値は -50,000 以上 50,000 以下でかつ 0 ではない整数の中から一様に選ばれる。具体的には次のような擬似コードで座標の値を決める。
x = 123456789
y = 362436069
z = 521288629
w = seed
for i = 1 to 5000
for j = 1 to 200
t = x ^ (x << 11)
x = y
y = z
z = w
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))
v = w % 100000 - 50000
if v >= 0 then
v = v + 1
(i 番目の点の座標の j 番目の値) = v
ここで seed は入力の seed の値である。
また変数 x, y, z, w, t は 32 ビットの符号なし整数型とし、= で代入、^ でビットごとの排他的論理和(XOR)、<< でビット左シフト、>> でビット右シフトを表すとする。
出力
ちょうど 4,999 行出力せよ。各行には 2 つの整数 p, q が書かれていなければならず、これは点 p と点 q を結ぶことを表す。
出力の末尾にも改行をいれること。
入力例1
1
出力例1
出力は膨大な量になるため記載しませんが、このケースに対する最小のコストは約 3739.378294998 です。
入力例2
2
出力例2
このケースに対する最小のコストは約 3741.147062644 です。