← 返回题目列表

AtCoder · arc021_4

D. 大致最小生成树

中文机器翻译题面 查看原题

問題文

这个世界是 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 如果成本在两倍以内则接受 。 除以


入力

输入是按以下格式从标准输入给出的。

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 。