Codeforces1059C. Sequence Transformation 好题 没做出来 数学思维

C. Sequence Transformation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's call the following process a transformation of a sequence of length nn.

If the sequence is empty, the process ends. Otherwise, append the ​​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 nn integers: the greatest common divisors of all the elements in the sequence before each deletion.

You are given an integer sequence 1,2,…,n1,2,…,n. Find the lexicographically maximum result of its transformation.

A sequence a1,a2,…,ana1,a2,…,an is lexicographically larger than a sequence b1,b2,…,bnb1,b2,…,bn, if there is an index ii such that aj=bjaj=bj for all j<ij<i, and ai>biai>bi.

Input

The first and only line of input contains one integer nn (1≤n≤1061≤n≤106).

Output

Output nn integers  — the lexicographically maximum result of the transformation.

Examples

input

Copy

3

output

Copy

1 1 3

input

Copy

2

output

Copy

1 2

input

Copy

1

output

Copy

1

Note

In the first sample the answer may be achieved this way:

• Append GCD(1,2,3)=1(1,2,3)=1, remove 22.
• Append GCD(1,3)=1(1,3)=1, remove 11.
• Append GCD(3)=3(3)=3, remove 33.

We get the sequence [1,1,3][1,1,3] as the result.

题意：给定一个数n，设一个从1到n的序列，每次删掉一个序列中的数，求按字典序最大化的GCD序列

分析：首先有一个显而易见的结论：对于任意排列，b序列中的前n/2个数总是1。
原因是相邻的两个数互质。
现在我们来考虑一个长度大于3的排列，怎样才能将b序列的字典序最大。
根据字典序的定义，我们需要最大化每一次进入队列的gcd。
即，当前最大就是整体最好的选择。
那么我们对于任意两个相邻的数，都有一个选择：删除其中的奇数或删除其中的偶数。
我们应该全部删除奇数或者全部删除偶数，不然就会有两个数相邻，从而出现gcd=1使得答案不优。
如果我们删除偶数，我们就会发现有ai=1使得这个序列的gcd=1而使得答案不优。
所以我们对于每个序列，都要删除奇数，使得gcd*=2。
观察操作后的序列
    a{2,4,...,(n&1)?(n-1):(n)}
我们可以将它看成
    a{2*1,2*2,2*3,...,2*(n/2)}
这样我们就把问题转化成了一个长度为n/2的子问题。
对于1<=n<=3的序列或长度小于等于3的子问题，题目的样例就是我们想要的结果，特判即可。
复杂度实际上是O(n)的

代码实现：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
int main(){
 
   
        int n;
    cin>>n;
    int k=1;
    while(n)
    {
        if(n==3)
        {
            cout<<k<<" "<<k<<" "<<k*3<<endl;
            return 0;
        }
        for(int i=0; i<(n+1)/2; i++)
            cout<<k<<" ";
        n/=2;
        k*=2;
    }
    return 0;
}