codeforces-scrape

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

1858C.md (2812B)


      1 Source: https://codeforces.com/problemset/problem/1858/C
      2 
      3 C. Yet Another Permutation Problem
      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 Alex got a new game called "GCD permutations" as a birthday present. Each round of this game proceeds as follows:
     22 
     23 * First, Alex chooses a permutation$^{\dagger}$ $a_1, a_2, \ldots, a_n$ of integers from $1$ to $n$.
     24 * Then, for each $i$ from $1$ to $n$, an integer $d_i = \gcd(a_i, a_{(i \bmod n) + 1})$ is calculated.
     25 * The score of the round is the number of distinct numbers among $d_1, d_2, \ldots, d_n$.
     26 
     27 Alex has already played several rounds so he decided to find a permutation $a_1, a_2, \ldots, a_n$ such that its score is as large as possible.
     28 
     29 Recall that $\gcd(x, y)$ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of numbers $x$ and $y$, and $x \bmod y$ denotes the remainder of dividing $x$ by $y$.
     30 
     31 $^{\dagger}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
     32 
     33 Input
     34 
     35 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     36 
     37 Each test case consists of one line containing a single integer $n$ ($2 \le n \le 10^5$).
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     40 
     41 Output
     42 
     43 For each test case print $n$ distinct integers $a_{1},a_{2},\ldots,a_{n}$ ($1 \le a_i \le n$) — the permutation with the largest possible score.
     44 
     45 If there are several permutations with the maximum possible score, you can print any one of them.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 4
     53 
     54 5
     55 
     56 2
     57 
     58 7
     59 
     60 10
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 1 2 4 3 5 
     67 1 2 
     68 1 2 3 6 4 5 7 
     69 1 2 3 4 8 5 10 6 9 7
     70 ```
     71 
     72 Note
     73 
     74 In the first test case, Alex wants to find a permutation of integers from $1$ to $5$. For the permutation $a=[1,2,4,3,5]$, the array $d$ is equal to $[1,2,1,1,1]$. It contains $2$ distinct integers. It can be shown that there is no permutation of length $5$ with a higher score.
     75 
     76 In the second test case, Alex wants to find a permutation of integers from $1$ to $2$. There are only two such permutations: $a=[1,2]$ and $a=[2,1]$. In both cases, the array $d$ is equal to $[1,1]$, so both permutations are correct.
     77 
     78 In the third test case, Alex wants to find a permutation of integers from $1$ to $7$. For the permutation $a=[1,2,3,6,4,5,7]$, the array $d$ is equal to $[1,1,3,2,1,1,1]$. It contains $3$ distinct integers so its score is equal to $3$. It can be shown that there is no permutation of integers from $1$ to $7$ with a score higher than $3$.