luogu#P11058. 合并香蕉

合并香蕉

题目背景

题目描述

nn 条大香蕉,第 ii 条大香蕉可简化为一个正整数二元组 (ai,ki)(a_i,k_i),其中 2ki102\le k_i\le 10

初始时有 nn 堆大香蕉,第 ii 堆只包含第 ii 条大香蕉。

每次可以选择不同的两堆合并,合并时会损耗香蕉的大小。

具体地,如果第 ii 条香蕉参与了合并,则其大小 aia_i 会变为原来的 1ki\frac{1}{k_i} 倍。

参与了合并:合并前在两堆香蕉中的某一堆中。

你想把大香蕉们合为一堆,由于香蕉越大越好,你需要让操作结束后所有的 aia_i 之和越大越好

考虑到求出最优解可能会比较困难,你只需要尽可能接近标准答案即可,具体参见评分标准

为了防止你乱输出一个数,你还需要输出方案,具体参见输出格式

输入格式

第一行一个正整数代表 nn

接下来 nn 行,每行两个正整数代表 ai,kia_i,k_i

输出格式

输出 n1n-1 行,每行两个数 x,yx,y 代表合并第 xx 堆和第 yy 堆。

对于第 ii 次合并,我们记新形成的香蕉堆是第 n+in+i 堆,而原来的两个香蕉堆(第 xx 堆、第 yy 堆)从此将被视为不存在 ,所以之后的合并中不允许调用 xxyy,否则你将会爆零。

3
1 10
27 3
32 2
1 2
4 3

提示

样例解释

该样例输出对应的操作结束后满足 a=(0.01,3,16)a=(0.01,3,16),对应的 aia_i 之和为 19.0119.01

另外,如果输出如下,则操作结束后满足 a=(0.01,9,8)a=(0.01,9,8),对应的 aia_i 之和为 17.0117.01,可以获得 44 分。

1 3
2 4

评分标准

对于每个测试点,我们采用如下方式评分:

  • 如果你的输出不合法,得 00 分。
  • 否则设你输出的方案对应的操作结束后的 aia_i 之和为 ff,标准答案输出的方案对应的操作结束后的 aia_i 之和为 ansans,则你的得分 $s=\lfloor \max\{0,10-\log_{10} \max\{1,\frac{ans-f}{\epsilon}\}\}\rfloor$ 分,其中 ϵ=105\epsilon=10^{-5}

数据范围

本题共有 1010 个测试点,每个测试点 1010 分。

测试点编号 n=n= 特殊性质
11 33
22 55
33 1010
44 2020
55 100100
66 10310^3
77 105310^5-3 ai=1a_i=1ki=2k_i=2
88 105210^5-2 ai=1a_i=1
99 105110^5-1 ki=2k_i=2
1010 10510^5

对于所有数据,保证 3n1053\le n\le 10^51ai1051\le a_i\le 10^52ki102\le k_i\le 10