P6241 [eJOI 2019] Tower

Jernej feels very bored at night, so he invents a game. He wants to use number cards to build a tower. At the beginning, he writes the number $1$ on a card. Jernej may write a new number on another card and place it on the top of the tower. **This new number must be equal to the sum of the numbers in some consecutive segment of the current tower**. In other words, suppose there are already $n$ numbers in the tower. You may choose any segment $[l,u]$ in the tower, compute the sum of this segment, and add the resulting new number to the top of the tower, where $1\le l\le u\le n$. Jernej wants to build $T$ towers (equivalently, multiple queries). The top number of each tower is one of $T$ (possibly different) target numbers he wants. You need to help him find the minimum number of steps to build these towers and output a corresponding plan.

The first line contains an integer $T$, the number of towers. The next $T$ lines each contain an integer $q$, meaning Jernej wants to build a tower whose top number is $q$. It is guaranteed that a solution exists.

For each query $q$: - Output one line containing an integer $s$ ($0\le s\le 10^3$), the minimum number of steps. - Then output $s$ lines, each containing two integers $l,u$ separated by a space, describing the plan to build the tower (print earlier operations first).

#### Special Judge Scoring Rules This problem has $10$ test points. For each test point, the scoring rules are: - For any tower in the test point, if the **minimum number of steps** output by your program is **exactly the same** as the standard answer, then you will get $10$ points for this test point. - For any tower in the test point, if your program’s output is incorrect, you get $0$ points (during judging, if the output is incomplete you may get UKE). - If your answer is **not optimal but still correct**, then for the $i$-th tower in this test point, your score is $\text{score}_i =1+\dfrac{\text{minimum steps}}{\text{solution steps}}\times 7$, where $\text{minimum steps}$ is the minimum number of steps in the correct answer, and $\text{solution steps}$ is the answer output by your program. The final score of this test point is $\min\limits_{i\in [1,T]} \{\text{score}_i\}$. Round up to two decimal places. #### Sample Input/Output Explanation **Query 1 Explanation**: - Jernej wants to build a tower with top number $2$. Initially the tower is $\{1\}$ (the left side is the bottom and the right side is the top). - Step 1: choose segment $[1,1]$, sum all elements in $\{1\}$ to get $1$, now the tower is $\{1,1\}$. - Step 2: choose segment $[1,2]$, sum all elements in $\{1,1\}$ to get $2$, now the tower is $\{1,1,2\}$. The requirement of the query is now satisfied. **Query 2 Explanation**: - There is more than one way to build a tower whose top is $3$. Besides the one in the sample output, the following is also a correct answer: ```plain 1 1 1 2 2 3 ``` #### Constraints **This problem uses bundled testdata and has 7 subtasks**. - 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 cases - 20 points): no additional constraints. For all testdata, it is guaranteed that $1\le T\le 10^3,1\le q\le 10^{18}$. #### Notes The original problem is from: [eJOI2019](https://www.ejoi2019.si) Problem D. [Tower](https://www.ejoi2019.si/static/media/uploads/tasks/tower-isc.pdf). Translation provided by: @[```_Wallace_```](https://www.luogu.com.cn/user/61430). Translated by ChatGPT 5