luogu#P11058. 合并香蕉
合并香蕉
题目背景
题目描述
有 条大香蕉,第 条大香蕉可简化为一个正整数二元组 ,其中 。
初始时有 堆大香蕉,第 堆只包含第 条大香蕉。
每次可以选择不同的两堆合并,合并时会损耗香蕉的大小。
具体地,如果第 条香蕉参与了合并,则其大小 会变为原来的 倍。
参与了合并:合并前在两堆香蕉中的某一堆中。
你想把大香蕉们合为一堆,由于香蕉越大越好,你需要让操作结束后所有的 之和越大越好。
考虑到求出最优解可能会比较困难,你只需要尽可能接近标准答案即可,具体参见评分标准。
为了防止你乱输出一个数,你还需要输出方案,具体参见输出格式。
输入格式
第一行一个正整数代表 。
接下来 行,每行两个正整数代表 。
输出格式
输出 行,每行两个数 代表合并第 堆和第 堆。
对于第 次合并,我们记新形成的香蕉堆是第 堆,而原来的两个香蕉堆(第 堆、第 堆)从此将被视为不存在 ,所以之后的合并中不允许调用 和 ,否则你将会爆零。
3
1 10
27 3
32 2
1 2
4 3
提示
样例解释
该样例输出对应的操作结束后满足 ,对应的 之和为 。
另外,如果输出如下,则操作结束后满足 ,对应的 之和为 ,可以获得 分。
1 3
2 4
评分标准
对于每个测试点,我们采用如下方式评分:
- 如果你的输出不合法,得 分。
- 否则设你输出的方案对应的操作结束后的 之和为 ,标准答案输出的方案对应的操作结束后的 之和为 ,则你的得分 $s=\lfloor \max\{0,10-\log_{10} \max\{1,\frac{ans-f}{\epsilon}\}\}\rfloor$ 分,其中 。
数据范围
本题共有 个测试点,每个测试点 分。
测试点编号 | 特殊性质 | |
---|---|---|
无 | ||
且 | ||
无 |
对于所有数据,保证 ,,。