[eJOI2019] 塔

Jernej 在晚上感到很无聊，于是他发明了一个游戏。他想要用数字卡片生成一个塔。一开始，他在一张卡片上写下了一个数字 $1$。 Jernej 可以再另一张写下一个新的数字并放在塔顶。 **这个新的数字必须等于之前塔中某一连续段的数字之和** 。也就是说，假设现在塔中已有 $n$ 个数字，你可以任意选取塔中的一段 $[l,u]$ ，并对这一段求和，将得到的新数字添加至塔顶，其中 $1\le l\le u\le n$。 Jernej 想要生成 $T$ 个塔（相当于多组询问），每个塔顶都是 $T$ 个可能不同的他想要的数字。你需要帮助他求出生成这些塔的最小步数及其方案。

第一行：一个整数 $T$，表示塔的个数； 接下来 $T$ 行，一行一个整数 $q$，表示现在 Jernej 想生成一个塔顶数字为 $q$ 的塔。 保证有解。

对于每个询问 $q$： - 输出一行，包含一个整数 $s$ （$0\le s\le 10^3$），表示最小步数。 - 接下来 $s$ 行，每行两个由空格隔开的整数 $l,u$，表示建生成塔的方案（操作时间早的先输出）。

3
2
3
7

2
1 1
1 2
3
1 1
2 2
1 3
4
1 1
1 2
2 3
1 4​

#### 【Special Judge 计分标准】 本题共 $10$ 个测试点。对于每个测试点，计分规则如下： - 对于测试点中的任意一个塔，如果你的程序输出的 **最小步数** 与标准答案 **均一致** ，那么这个测试点你会得到 $10$ 分。 - 对于测试点中的任意一个塔，如果你的程序输出的答案是错误的，那么得 $0$ 分（评测时如果发现输出不完全可能会得到 UKE）。 - 如果你的答案并 **不是最优解但不是错误的** ，那么对于该测试点中的第 $i$ 个塔，你得到的分数为 $\text{score}_i =1+\dfrac{\text{minimum steps}}{\text{solution steps}}\times 7$，其中 $\text{minimum steps}$ 表示正确答案的最小步数，$\text{solution steps}$ 表示你的程序输出的答案。最终这个测试点的得分为 $\min\limits_{i\in [1,T]} \{\text{score}_i\}$。向上取两位小数。 #### 【输入输出样例解释】 **询问 1 解释**： - Jernej 想要生成造一个塔顶数为 $2$ 的塔。起初塔为 $\{1\}$（左边表示塔底，右边表示塔顶）； - 第一步，选取子段 $[1,1]$，对 $\{1\}$ 中的所有元素求和，得到 $1$，现在塔为 $\{1,1\}$； - 第二步，选取子段 $[1,2]$，对 $\{1,1\}$ 中的所有元素求和，得到 $2$，现在塔为 $\{1,1,2\}$。此时已经达到了询问的要求。 **询问 2 解释**： - 要生成塔顶为 $3$ 的塔不止一种方法。除了样例输出的一种之外，下面的也是正确答案： ```plain 1 1 1 2 2 3 ``` #### 【数据规模与约定】 **本题采用多测试点捆绑测试，共有 7 个子任务**。 - Subtask 1（1 test case - 10 points）：$T\le 10,q\le 10$。 - Subtask 2（1 test case - 10 points）：$T\le 20,q\le 20$。 - Subtask 3（1 test case - 10 points）：$T= 100,q\le 100$。 - Subtask 4（1 test case - 10 points）：$T= 10^3,q\le 10^4$。 - Subtask 5（1 test case - 10 points）：$T= 10^3,q\le 10^5$。 - Subtask 6（1 test case - 10 points）：$T= 10^3,q\le 10^6$。 - Subtask 7（1 test case - 10 points）：$T= 10^3,q\le 10^9$。 - Subtask 8（1 test case - 10 points）：$T= 10^3,q\le 10^{12}$。 - Subtask 9（2 test case - 20 points）：无其他限制。 对于所有数据，保证 $1\le T\le 10^3,1\le q\le 10^{18}$ #### 【说明】 原题来自：[eJOI2019](https://www.ejoi2019.si) Problem D. [Tower](https://www.ejoi2019.si/static/media/uploads/tasks/tower-isc.pdf)。 翻译提供：@[```_Wallace_```](https://www.luogu.com.cn/user/61430)