codeforces-scrape

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

1469D.md (2177B)


      1 Source: https://codeforces.com/problemset/problem/1469/D
      2 
      3 D. Ceil Divisions
      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 You have an array $a_1, a_2, \dots, a_n$ where $a_i = i$.
     22 
     23 In one step, you can choose two indices $x$ and $y$ ($x \neq y$) and set $a_x = \left\lceil \frac{a_x}{a_y} \right\rceil$ (ceiling function).
     24 
     25 Your goal is to make array $a$ consist of $n - 1$ ones and $1$ two in no more than $n + 5$ steps. Note that you don't have to minimize the number of steps.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     30 
     31 The first and only line of each test case contains the single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the length of array $a$.
     32 
     33 It's guaranteed that the sum of $n$ over test cases doesn't exceed $2 \cdot 10^5$.
     34 
     35 Output
     36 
     37 For each test case, print the sequence of operations that will make $a$ as $n - 1$ ones and $1$ two in the following format: firstly, print one integer $m$ ($m \le n + 5$) — the number of operations; next print $m$ pairs of integers $x$ and $y$ ($1 \le x, y \le n$; $x \neq y$) ($x$ may be greater or less than $y$) — the indices of the corresponding operation.
     38 
     39 It can be proven that for the given constraints it's always possible to find a correct sequence of operations.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 2
     47 3
     48 4
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 2
     55 3 2
     56 3 2
     57 3
     58 3 4
     59 4 2
     60 4 2
     61 ```
     62 
     63 Note
     64 
     65 In the first test case, you have array $a = [1, 2, 3]$. For example, you can do the following:
     66 
     67 1. choose $3$, $2$: $a_3 = \left\lceil \frac{a_3}{a_2} \right\rceil = 2$ and array $a = [1, 2, 2]$;
     68 2. choose $3$, $2$: $a_3 = \left\lceil \frac{2}{2} \right\rceil = 1$ and array $a = [1, 2, 1]$.
     69 
     70 You've got array with $2$ ones and $1$ two in $2$ steps.
     71 
     72 In the second test case, $a = [1, 2, 3, 4]$. For example, you can do the following:
     73 
     74 1. choose $3$, $4$: $a_3 = \left\lceil \frac{3}{4} \right\rceil = 1$ and array $a = [1, 2, 1, 4]$;
     75 2. choose $4$, $2$: $a_4 = \left\lceil \frac{4}{2} \right\rceil = 2$ and array $a = [1, 2, 1, 2]$;
     76 3. choose $4$, $2$: $a_4 = \left\lceil \frac{2}{2} \right\rceil = 1$ and array $a = [1, 2, 1, 1]$.