Codeforces Round #479 (Div. 3) D. Divide by three, multiply by two

D. Divide by three, multiply by two

•题意

给你一个数 x，有以下两种操作，x 可以任选其中一种操作得到数 y

1.如果x可以被3整除，y=x/3

2.y=x*2

y 再执行上述两种操作的一种得到数 z；

　　接着对 z 得到......

　　这样依次执行了 n-1 次会得到 n 个数；

　　现在给你这 n 个数，让你按照上述规则给这 n 个数排序，使得其满足

　　a₁=x , a₂=y , a₃=z , ........

•思路

对于任意一个数 p，能通过两类操作得到：

①p=3p /3

②p=x/2 *2

因为GCD(2,3) = 1，所以右边的等式是不可能成立的；

　　所以 p只能由①②中的一种情况得到；

　　并且这 n 个数各不相同；

　　那么，任意选取一个数，依次向前推到第一个数，依次向后推即可得到答案；

•代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

map<ll,int> mp;

int main()

{

    int n;

    cin>>n;

    ll x;

    for(int i=;i<n;i++)

    {

        cin>>x;

        mp[x]=;

    }

    ll cur=x;

    while()

    {

        if(cur%==&&mp.count(cur/))

            cur/=;

        else if(mp.count(cur*))

            cur*=;

        else //直到没有前一个 此时为第一个数

            break;

    }

    while() //从前往后推 乘2 或 除3

    {

        cout<<cur<<' ';

        if(mp.count(cur*))

            cur*=;

        else if(cur%==&&mp.count(cur/))

            cur/=;

        else

            break;

    }

}

巴特西

Codeforces Round #479 (Div. 3) D. Divide by three, multiply by two

D. Divide by three, multiply by two

•题意

•思路

•代码

最新文章

热门文章