Cod sursa(job #102168)

Utilizator dominoMircea Pasoi domino Data 14 noiembrie 2007 01:00:25
Problema Ecuatie Scor Ascuns
Compilator cpp Status done
Runda Marime 2.22 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

#define FIN "ecuatie.in"
#define FOUT "ecuatie.out"
#define mp make_pair
#define pb push_back
#define ll long long 

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

string format(ll c, ll v)
{
    char t[64];

    if (c != 1 && c != -1)
    {
        if (v < 0)
            sprintf(t, "(%lldx+%lld)", c, -v);
        else
            sprintf(t, "(%lldx-%lld)", c, v);
    }
    else
    if (c == -1)
    {
        if (v < 0)
            sprintf(t, "(-x+%lld)", -v);
        else
            sprintf(t, "(-x-%lld)", v);
    }
    else
    {
        if (v < 0)
            sprintf(t, "(x+%lld)", -v);
        else
            sprintf(t, "(x-%lld)", v);
    }
    return t;
}

inline void insert(ll a, ll x1, ll y1, ll b, ll x2, ll y2)
{
    string s = "";

    if ((a*x1)%y1 || (b*x2)%y2) return;
    s += format(a, (a*x1)/y1); 
    s += format(b, (b*x2)/y2); 
    V.pb(mp(mp(a, -(a*x1)/y1), s));
}

ll gcd(ll a, ll b)
{
    return !b ? a : gcd(b, a%b);
}

int main(void)
{
    ll delta, t, d, x1, y1, x2, y2;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d %d %d %d", &A, &B, &C, &K);
   
    delta = (ll)B*B - (ll)4*A*C;
    t = (ll)sqrt((double) delta);

    if (t*t != delta)
    {
        printf("-1\n");
        return 0; 
    }

    x1 = -B+t; y1 = 2*A;
    d = gcd(labs(x1), labs(y1));
    x1 /= d; y1 /= d;
    x2 = -B-t; y2 = 2*A;
    d = gcd(labs(x2), labs(y2));
    x2 /= d; y2 /= d;

    for (d = 1; d*d <= abs(A); ++d)
    {
        if (A%d) continue;
        insert(d, x1, y1, A/d, x2, y2);
        insert(A/d, x2, y2, d, x1, y1);
        insert(-d, x1, y1, -A/d, x2, y2);
        insert(-A/d, x2, y2, -d, x1, y1);
        if (d*d == abs(A)) continue;
        insert(A/d, x1, y1, d, x2, y2);
        insert(d, x2, y2, A/d, x1, y1);
        insert(-A/d, x1, y1, -d, x2, y2);
        insert(-d, x2, y2, -A/d, x1, y1);
    }

    if (K > (int)V.size())
    {
        printf("-1\n");
        return 0; 
    }

    sort(V.begin(), V.end());
    printf("%s\n", V[K-1].second.c_str());

    return 0;
}