Cod sursa(job #167785)

Utilizator tm_raduToma Radu tm_radu Data 30 martie 2008 02:25:21
Problema Ecuatie Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.16 kb
#include <stdio.h>
#include <vector>
#include <math.h>
#define abs(a) ((a) > 0 ? (a) : -(a))
#define nr (sol.size())
using namespace std;

int a, b, c, k;
int i, j, h, g, d;
long long int delta;
double x1, x2;
int p1, p2, q1, q2;
struct e {
	int p1, p2, q1, q2;
};
vector<e> sol;

void Verif(int div);
void Qsort(int st, int dr);
void Print();

int main()
{
	freopen("ecuatie.in", "r", stdin);
	freopen("ecuatie.out", "w", stdout);
	scanf("%d %d %d %d", &a, &b, &c, &k);
	j = (int)sqrt((double)abs(a));
	long long int v1 = b, v2 = a, v3 = c;
	delta = v1*v1 - 4*v2*v3;
	h = (int)sqrt((double)delta);
	// no solution
	if ( delta != h*h )
	{
		printf("-1\n");
		return 0;
	}
	x1 = (double)(-b - h)/(double)(2*a);
	x2 = (double)(-b + h)/(double)(2*a);
	e str; str.p1 = str.p2 = str.q1 = str.q2 = 0;
	sol.push_back(str);
	// checking
	for ( i = 1; i <= j; i++ )
		if ( a % i == 0 )
		{
			Verif(i);
			Verif(-i);
			Verif(a/i);
			Verif(-a/i);
		}
	Qsort(1, nr-1);
    if ( nr <= k ) printf("-1\n");
    else Print();

    return 0;
}

void Verif(int div)
{
    int ok;
    // first case
	p1 = div;
	double v = ((double)-x1*(double)div);
	q1 = (int)(v);
	p2 = a/div;
	v = ((double)-x2*(double)(a/div));
    q2 = (int)v;
	if ( p1*p2 == a && (p2*q1 + p1*q2) == b && q1*q2 == c )
    {
        e pct;
        pct.p1 = p1; pct.p2 = p2; pct.q1 = q1; pct.q2 = q2;
        ok = 1;
        for ( int g = 1; g < nr; g++ )
            if ( sol[g].p1 == pct.p1 && sol[g].p2 == pct.p2 && sol[g].q1 == pct.q1 && sol[g].q2 == pct.q2 ) ok = 0;
		if ( ok ) sol.push_back(pct);
    }
    // second case
    p1 = div;
    v = ((double)-x2*(double)div);
    q1 = (int)v;
    p2 = a/div;
    v = ((double)-x1*(double)(a/div));
    q2 = (int)v;
	if ( p1*p2 == a && (p2*q1 + p1*q2) == b && q1*q2 == c )
    {
        e pct;
        pct.p1 = p1; pct.p2 = p2; pct.q1 = q1; pct.q2 = q2;
        ok = 1;
		for ( int g = 1; g < nr; g++ )
			if ( sol[g].p1 == pct.p1 && sol[g].p2 == pct.p2 && sol[g].q1 == pct.q1 && sol[g].q2 == pct.q2 ) ok = 0;
		if ( ok ) sol.push_back(pct);
    }
}

void Qsort(int st, int dr)
{
    int i = st-1;
    int j = dr+1;
    do
    {
        do { i++; } while ( sol[i].p1 < sol[st].p1 || (sol[i].p1 == sol[st].p1 && sol[i].q1 < sol[st].q1) );
        do { j--; } while ( sol[st].p1 < sol[j].p1 || (sol[st].p1 == sol[j].p1 && sol[st].q1 < sol[j].q1) );
        if ( i <= j )
        {
            e aux = sol[i];
            sol[i] = sol[j];
            sol[j] = aux;
        }
    } while ( i <= j );
    if ( i < dr ) Qsort(i, dr);
    if ( st < j ) Qsort(st, j);
}

void Print()
{
    p1 = sol[k].p1;
    p2 = sol[k].p2;
    q1 = sol[k].q1;
    q2 = sol[k].q2;
    printf("(");
    if ( p1 == 1 ) printf("x");
    if ( p1 == -1 ) printf("-x");
    if ( p1 != 1 && p1 != -1 ) printf("%dx", p1);
    if ( q1 >= 0 ) printf("+%d)(", q1);
    else           printf("%d)(", q1); 
    if ( p2 == 1 ) printf("x");
    if ( p2 == -1 ) printf("-x");
    if ( p2 != 1 && p2 != -1 ) printf("%dx", p2);
    if ( q2 >= 0 ) printf("+%d)\n", q2);
    else           printf("%d)\n", q2); 
}