codeforces-scrape

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

1059C.md (1534B)


      1 Source: https://codeforces.com/problemset/problem/1059/C
      2 
      3 C. Sequence Transformation
      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 Let's call the following process a transformation of a sequence of length $n$.
     22 
     23 If the sequence is empty, the process ends. Otherwise, append the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) (GCD) of all the elements of the sequence to the result and remove one arbitrary element from the sequence. Thus, when the process ends, we have a sequence of $n$ integers: the greatest common divisors of all the elements in the sequence before each deletion.
     24 
     25 You are given an integer sequence $1, 2, \dots, n$. Find the lexicographically maximum result of its transformation.
     26 
     27 A sequence $a_1, a_2, \ldots, a_n$ is lexicographically larger than a sequence $b_1, b_2, \ldots, b_n$, if there is an index $i$ such that $a_j = b_j$ for all $j \lt i$, and $a_i \gt b_i$.
     28 
     29 Input
     30 
     31 The first and only line of input contains one integer $n$ ($1\le n\le 10^6$).
     32 
     33 Output
     34 
     35 Output $n$ integers  — the lexicographically maximum result of the transformation.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 3
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 1 1 3
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 2
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 1 2
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 1
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 1
     73 ```
     74 
     75 Note
     76 
     77 In the first sample the answer may be achieved this way:
     78 
     79 * Append GCD$(1, 2, 3) = 1$, remove $2$.
     80 * Append GCD$(1, 3) = 1$, remove $1$.
     81 * Append GCD$(3) = 3$, remove $3$.
     82 
     83 We get the sequence $[1, 1, 3]$ as the result.