2015年1月30日 星期五

2015/01/30 Codeforces 490D. Chocolate

// http://codeforces.com/contest/490/problem/D
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

ll a[2], b[2];
ll s[2];

int two[2], three[2];

ll gcd(ll x, ll y)
{
    while( x && y )
    {
        if( x < y ) swap(x, y);
        x %= y;
    }

    return x+y;
}

int main()
{
    for(int i = 0; i < 2; i++)
    {
        cin>>a[i]>>b[i];
        s[i] = a[i]*b[i];

        while( s[i]%2 == 0 )
        {
            s[i] /= 2;
            two[i]++;
        }

        while( s[i]%3 == 0 )
        {
            s[i] /= 3;
            three[i]++;
        }
    }

    if( s[0] != s[1] )
    {
        puts("-1");
        return 0;
    }

    ll div[2] = {1, 1};

    int Ans = 0;

    while( three[0] != three[1] )
    {
        Ans++;

        int x = three[0] > three[1] ? 0 : 1;
        three[x]--; two[x]++;
        div[x] *= 3;

        if( a[x]%3 == 0 ) a[x] = a[x]/3*2;
        else b[x] = b[x]/3*2;
    }

    while( two[0] != two[1] )
    {
        Ans++;

        int x = two[0] > two[1] ? 0 : 1;
        two[x]--;
        div[x] *= 2;

        if( a[x]%2 == 0 ) a[x] = a[x]/2;
        else b[x] = b[x]/2;
    }

    cout<<Ans<<endl;

    for(int i = 0; i < 2; i++)
        cout<<a[i]<<" "<<b[i]<<endl;

}

沒有留言:

張貼留言