这是一道提交答案题。

题目描述

S 老师下个学期要开设一门“折纸”课，上课需要用到的一大材料就是白纸。由于这门课的水平非常高，所以对纸张的尺寸要求也很高。根据教学计划，这门课一共需要 $n$ 个纸片，其中必须满足第 $i$ 个纸片的长为 $a_i$，宽为 $b_i$（以下称这样的纸片为 $a_i \times b_i$ 的纸片）。

S 老师决定按照如下方法制作出所需的纸片：

• 购买一张任意尺寸的矩形纸片
• 进行下列操作任意次：
  • 将已有的某个矩形纸片，按横向或纵向切分为两个新的矩形纸片
  • 丢弃已有的某个矩形纸片

最终，需要保证恰好剩下 $n$ 个纸片，且与所需的 $n$ 个纸片的尺寸对应相等。这里我们认为，通过旋转 $90^\circ$ 变得相同的两个纸片也是相同的，即 $p \times q$ 的纸片与 $q \times p$ 的纸片是相同的。

S 老师希望初始时购买的矩形纸片的面积尽可能小，并且希望初始购买的纸片的一条边长尽可能落在 $[L, R]$ 中；请你帮帮他吧！

输入格式

这是一道提交答案题，共有10组输入数据，这些数据命名为 1.in ~ 10.in。

每个输入文件仅包含一个测试数据。

• 第一行包含三个空格隔开的正整数 $n, L, R$。
• 接下来 $n$ 行，每行包含空格隔开的两个整数：其中第 $i$ 行的两个数分别为 $a_i$ 和 $b_i$。

输出格式

对于每组输入数据，你需要提交相应的输出文件 1.out ~ 10.out。

• 第一行包含空格隔开的三个正整数 $m, A, B$，表示你的方案中初始购买了 $A \times B$ 的纸片，并进行了 $m$ 次切分操作
  • 你需要保证 $m \leq 10^4, A \leq 10^9, B \leq 10^9$
  • 你需要尽可能满足 $L \leq A \leq R$，或 $L \leq B \leq R$
  • 你需要使 $A \cdot B$ 尽量小
• 接下来 $m$ 行，每行依次表示一个切分操作；设某一行包含空格隔开的六个正整数 $p_0, q_0, p_1, q_1, p_2, q_2$，则表示该次操作将一个 $p_0 \times q_0$ 的纸片切分为一个 $p_1 \times q_1$ 的纸片和一个 $p_2 \times q_2$ 的纸片
  • 你需要保证，以下两项至少有一项成立：
    • $p_0=p_1=p_2$ 且 $q_0=q_1+q_2$
    • $q_0=q_1=q_2$ 且 $p_0=p_1+p_2$
  • 你需要保证，在进行此操作之前，存在 $p_0 \times q_0$ 的纸片或 $q_0 \times p_0$ 的纸片（无论是初始购买的还是之前切分产生的）；进行此操作之后，符合该条件的纸片将减少一个
  • 进行此操作之后，将产生一个 $p_1 \times q_1$ 的纸片和一个 $p_2 \times q_2$ 的纸片
• 不输出丢弃纸片的操作
• 你需要保证，所有操作结束后，对于 $[1,n]$ 范围的每个 $i$，能依次完成以下过程：
  • 存在 $a_i \times b_i$ 的纸片或 $b_i \times a_i$ 的纸片，然后令符合该条件的纸片减少一个
• 上述内容输出完毕后，允许在新的若干行内输出任何其他内容，但每个输出文件的总大小不能超过 1 MB。我们建议你在此处写一些有意义的内容（如简要方法），以便于我们在考后进行统计分析。

评分方式

对于每个输入数据*.in，我们提供了对应的评分文件*.ans。评分文件的格式如下：

• 第一行为一个非负整数 $d$
• 接下来 10 行，每行一个整数；设其中第 $i$ 行的整数为 $S_i$

此外，设你给出的方案中初始购买的纸片面积为 $S=A \cdot B$，则按以下规则进行评分：

• 如果你的输出不符合【输出格式】的要求，包括但不限于切分操作次数过多、某次操作不合法、输出不完整、最终无法产生所需的 $n$ 个纸片等，则该测试点得 0 分
• 如果 $S \leq S_{10}$，则该测试点得 10 分
• 如果 $S_{10} < S \leq S_9$，则该测试点得 9 分
• 如果 $S_9 < S \leq S_8$，则该测试点得 8 分
• ……
• 如果 $S_2 < S \leq S_1$，则该测试点得 1 分
• 如果 $S > S_1$，则该测试点得 0 分
• 如果 $L \leq A \leq R$ 与 $L \leq B \leq R$ 均不满足，则该测试点额外扣除 $d$ 分，但至少得 0 分（不会倒扣分）

我们在你的主目录中paper文件夹内下发了所有输入文件、评分文件和判定程序checker，判定程序能帮你计算输出文件的得分。你可以按照下述方法使用判定程序：

• 打开一个终端（你可以使用快捷键Ctrl+Alt+T）
• 切换到工作目录，并确保有可执行权限

cd ~/paper/
chmod +x checker

• 例如，对 1 号测试点进行评分

./checker 1

• 对所有测试点进行评分

./checker

判定程序将会在屏幕上用英文输出相关信息，请仔细阅读。

最终测试时使用的判定程序与下发的判定程序的行为相同，除非你试图通过不合输出格式的输出文件攻击判定程序。

提示

对于 $d=0$ 的测试点，虽然你的方案中两条边的长度都不落在 $[L, R]$ 中不会带来分数的损失，但是这给出了某个能获得满分的方案中的某条边长度，你可以用来参考。你也可以通过综合观察输入文件中的 $L, R$ 与评分文件中的 $S_i$ 来更精确地确定可能较优的一条边长度。

另外，这个算式很可能对你解决第一个测试点有帮助：

$1 \times 2 \times 3 + 4 + 5 \times (6 \times (7 \times 8 + 9) + 10)$