Codeforces 977D. Divide by three, multiply by two

喜欢ヅ旅行 2022-04-05 08:42 253阅读 0赞

# Divide by three, multiply by two #

Polycarp likes to play with numbers. He takes some integer number x, writes it down on the board, and then performs with it n−1 operations of the two kinds:

divide the number x by 3 (x must be divisible by 3);  
multiply the number x by 2.  
After each operation, Polycarp writes down the result on the board and replaces x by the result. So there will be n numbers on the board after all.

You are given a sequence of length n — the numbers that Polycarp wrote down. This sequence is given in arbitrary order, i.e. the order of the sequence can mismatch the order of the numbers written on the board.

Your problem is to rearrange (reorder) elements of this sequence in such a way that it can match possible Polycarp’s game in the order of the numbers written on the board. I.e. each next number will be exactly two times of the previous number or exactly one third of previous number.

It is guaranteed that the answer exists.

### Input ###

The first line of the input contatins an integer number n (2≤n≤100) — the number of the elements in the sequence. The second line of the input contains n integer numbers a1,a2,…,an (1≤ai≤3⋅1018) — rearranged (reordered) sequence that Polycarp can wrote down on the board.

### Output ###

Print n integer numbers — rearranged (reordered) input sequence that can be the sequence that Polycarp could write down on the board.

It is guaranteed that the answer exists.

### Examples ###

##### input #####

6  
4 8 6 3 12 9

##### output #####

9 3 6 12 4 8

##### input #####

4  
42 28 84 126

##### output #####

126 42 84 28

##### input #####

2  
1000000000000000000 3000000000000000000

##### output #####

3000000000000000000 1000000000000000000

### Note ###

In the first example the given sequence can be rearranged in the following way: \[9,3,6,12,4,8\]. It can match possible Polycarp’s game which started with x=9.

--------------------

题意：  
给你一组数，这组数是由一个数经过除以三，乘以二变化来的，这个数也给了  
让你输出变化的顺序  
如给的是4 8 6 3 12 9  
那么答案就是 9 3 6 12 4 8  
结果一定是唯一的

这道题，脑袋不知道怎么了，周赛的时候做没有做出来，。，，  
回头补了一下，发现不是很难  
由于n比较小，  
第一种方式我采用的是暴力建链表  
对于任意两个数a b  
如果 a \* 3 == b || a = b \* 2  
那么就说明，在生成的序列中 a 在 b 的前面

--------------------

//暴力建立链表 
    
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    
    ll a[128];
    int l[128];
    bool f[128];
    int main()
    {
        
    	int n;
    	cin>>n;
    	memset(f,0,sizeof(f));
    	memset(l,-1,sizeof(l));
    	for(int i=0;i<n;i++)
    		cin>>a[i];
    	for(int i=0;i<n;i++)
    		for(int j=0;j<n;j++)
    		{
        
    			if(i==j)	continue;
    			if(a[i]*2==a[j]||a[i]==a[j]*3)	l[i]=j,f[j]=1;// a[i] 在前，a[j]在后 没有被用过的是头节点 
    		}
    	int t = -1;
    	for(int i=0;i<n;i++)
    		if(!f[i])
    		{
        
    			t = i;
    			break;
    		}
    	for(t;~t;t=l[t])
    		printf("%I64d%c",a[t]," \n"[t==-1]);
    	return 0;
    }

第二种方法是：  
我们经过观察到结果序列规律：  
能整除3的次数越多，优先级越高，次数相同的按照从小到大排列

于是我用pair<int,long long> 来存数，第一个存优先级，第二个存数  
对pair进行sort的时候，会自动按照first从小到大排序，first相等时按照second从小到大排序

--------------------

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 107;
    ll a[MAXN];
    ll f(ll x)
    {
        
    	ll ans = 0;
    	while(x%3==0)
    	{
        
    		x/=3;
    		ans++;
    	}
    	return ans;
    }
    int main()
    {
        
    	int n;
    	cin>>n;
    	vector<pair<int,ll> > v;
    	v.resize(n);
    	for(int i=0;i<n;i++)
    	{
        
    		scanf("%I64d",&v[i].second);
    		v[i].first = -f(v[i].second); 
    	}
    	sort(v.begin(),v.end());//pair<> 数组的性质，先按first从小到大排序，first相等时按照second从小到大排序 
    	for(int i=0;i<n;++i)
    		printf("%I64d%c",v[i].second," \n"[i==n-1]); 
    	return 0;
    }