codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```