1430C.md (1673B)
1 Source: https://codeforces.com/problemset/problem/1430/C 2 3 C. Numbers on Whiteboard 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Numbers $1, 2, 3, \dots n$ (each integer from $1$ to $n$ once) are written on a board. In one operation you can erase any two numbers $a$ and $b$ from the board and write one integer $\frac{a + b}{2}$ rounded up instead. 22 23 You should perform the given operation $n - 1$ times and make the resulting number that will be left on the board as small as possible. 24 25 For example, if $n = 4$, the following course of action is optimal: 26 27 1. choose $a = 4$ and $b = 2$, so the new number is $3$, and the whiteboard contains $[1, 3, 3]$; 28 2. choose $a = 3$ and $b = 3$, so the new number is $3$, and the whiteboard contains $[1, 3]$; 29 3. choose $a = 1$ and $b = 3$, so the new number is $2$, and the whiteboard contains $[2]$. 30 31 It's easy to see that after $n - 1$ operations, there will be left only one number. Your goal is to minimize it. 32 33 Input 34 35 The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases. 36 37 The only line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of integers written on the board initially. 38 39 It's guaranteed that the total sum of $n$ over test cases doesn't exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, in the first line, print the minimum possible number left on the board after $n - 1$ operations. Each of the next $n - 1$ lines should contain two integers — numbers $a$ and $b$ chosen and erased in each operation. 44 45 Example 46 47 Input 48 49 ``` 50 1 51 4 52 ``` 53 54 Output 55 56 ``` 57 2 58 2 4 59 3 3 60 3 1 61 ```