Cod sursa(job #102867)

Utilizator astronomyAirinei Adrian astronomy Data 14 noiembrie 2007 19:10:54
Problema Ecuatie Scor Ascuns
Compilator cpp Status done
Runda Marime 4.04 kb
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;

#define llong long long
#define pb push_back
#define mp make_pair
#define ABS(x) ((x) < 0 ? (-(x)) : (x))

vector< pair< pair<llong, llong>, string > > V;
llong A, B, C;
int K;

void baga(llong p1, llong q1, llong p2, llong q2)
{
    stringstream oss;
    string aux;
    
    q1 = q1*(-1), q2 = q2*(-1);
    oss << '(';
    if(p1 != 1 && p1 != -1) oss << p1;
    if(p1 == -1) oss << '-';
    oss << 'x';
    if(q1 < 0) oss << q1 << ')';
    else oss << '+' << q1 << ')';

    oss << '(';
    if(p2 != 1 && p2 != -1) oss << p2;
    if(p2 == -1) oss << '-';
    oss << 'x';
    if(q2 < 0) oss << q2 << ')';
    else oss << '+' << q2 << ')';

    aux = oss.str();

    V.pb( mp( mp(p1,q1), aux) );
}

llong gcd(llong a, llong b) { return a == 0 ? b : gcd(a%b, b); }

int check(llong d1, llong x1, llong y1)
{
    if( ABS(d1*x1) % ABS(y1) != 0 ) return 0;
    return 1;
}

void solve(void)
{
    llong delta, rd, x1, x2, k, d1, d2, y1, y2;

    delta = B*B-A*C*4;
    if(delta < 0) printf("-1\n"), exit(0);

    rd = (llong) sqrt( (double)delta );
    if(rd*rd != delta) printf("-1\n"), exit(0);

    if( ABS(-B-rd) % ABS(A*2) != 0 ) printf("-1\n"), exit(0);
    if( ABS(-B+rd) % ABS(A*2) != 0 ) printf("-1\n"), exit(0);

    x1 = (-B-rd), x2 = (-B+rd), y1 = y2 = (A*2);

    for(k = 1; k*k <= ABS(A); k++)
     if(ABS(A)%k == 0)
     {
        if(A > 0)
        {
            d1 = k, d2 = A/k;
            if(check(d1, x1, y1) && check(d2, x2, y2))
                baga(d1, d1*x1/y1, d2, d2*x2/y2),
                baga(-d1,-d1*x1/y1, -d2, -d2*x2/y2);
            if(d1 != d2)
            {
                d1 ^= d2, d2 ^= d1, d1 ^= d2;
                if(check(d1, x1, y1) && check(d2, x2, y2))
                    baga(d1, d1*x1/y1, d2, d2*x2/y2),
                    baga(-d1,-d1*x1/y1, -d2, -d2*x2/y2);
            }
            if(x1 != x2)
            {
                d1 = k, d2 = A/k;
                if(check(d1, x2, y1) && check(d2, x1, y2))
                    baga(d1, d1*x2/y1, d2, d2*x1/y1),
                    baga(-d1,-d1*x2/y1, -d2, -d2*x1/y1);
                if(d1 != d2)
                {
                    d1 ^= d2, d2 ^= d1, d1 ^= d2;
                    if(check(d1, x2, y1) && check(d2, x1, y2))
                    baga(d1, d1*x2/y1, d2, d2*x1/y1),
                    baga(-d1,-d1*x2/y1, -d2, -d2*x1/y1);
                }
            }
        }
        if(A < 0)
        {
            d1 = k, d2 = -(ABS(A)/k);
            if(check(d1, x1, y1) && check(d2, x2, y2))
                baga(d1, d1*x1/y1, d2, d2*x2/y1),
                baga(-d1,-d1*x1/y1, -d2, -d2*x2/y1);
            if(d1 != d2)
            {
                d1 ^= d2, d2 ^= d1, d1 ^= d2;
                if(check(d1, x1, y1) && check(d2, x2, y2))
                    baga(d1, d1*x1/y1, d2, d2*x2/y1),
                    baga(-d1,-d1*x1/y1, -d2, -d2*x2/y1);
            }
            if(x1 != x2)
            {
                d1 = k, d2 = -(ABS(A)/k);
                if(check(d1, x2, y1) && check(d2, x1, y2))
                baga(d1, d1*x2/y1, d2, d2*x1/y1),
                baga(-d1,-d1*x2/y1, -d2, -d2*x1/y1);
                if(d1 != d2)
                {
                    d1 ^= d2, d2 ^= d1, d1 ^= d2;
                    if(check(d1, x2, y1) && check(d2, x1, y2))
                    baga(d1, d1*x2/y1, d2, d2*x1),
                    baga(-d1,-d1*x2/y1, -d2, -d2*x1);
                }
            }
        }
     }

    sort(V.begin(), V.end());

    rd = V.size();
    
    if(K > V.size()) printf("-1\n"), exit(0);

    cout << V[K].second << '\n';
}

int main(void)
{
    freopen("ecuatie.in", "rt",stdin);
    freopen("ecuatie.out","wt",stdout);

    cin >> A >> B >> C >> K;
    K--;
    
    solve();

    return 0;
}