Cod sursa(job #252859)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 4 februarie 2009 23:33:11
Problema Ecuatie Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include<stdio.h>
#include<math.h>
#define mod(a) (a>0?a:-a)

FILE *fin=fopen("ecuatie.in","r"),
    *fout=fopen("ecuatie.out","w");

int A,B,C,X;
double delta,x1,x2;
struct produs{int p1,p2,q1,q2;};
produs D[50000];

int comp(int a,int b){
    if(D[a].p1>D[b].p1)
        return 1;
    if(D[a].p1<D[b].p1)
        return -1;
    if(D[a].q1>D[b].q1)
        return 1;
    if(D[a].q1<D[b].q1)
        return -1;
    return 0;
}

void swap(int a,int b){
    produs aux;
    aux=D[a];D[a]=D[b];D[b]=aux;
}

int valid(double a,int x,double b,int y){
    int ok1=0,ok2=0;
    if((double)(a*x)==(int)(a*x))
        ok1++;
    if((double)(b*y)==(int)(b*y))
        ok2++;
    return ok1&&ok2;
}
int main(){
    fscanf(fin,"%d %d %d %d",&A,&B,&C,&X);
    delta=B*B-4*A*C;
    x1=(-B-sqrt(delta))/(2*A);
    x2=(-B+sqrt(delta))/(2*A);

    int N=(int)sqrt(mod(A));
    int Nr=0;
    for(int d=1;d<=N;d++)
        if(A%d==0){

                if(valid(x1,d,x2,A/d)){
                    D[++Nr].p1=d,D[Nr].p2=A/d,D[Nr].q1=-x1*d,D[Nr].q2=-x2*(A/d);
                    D[++Nr].p1=-d,D[Nr].p2=-A/d,D[Nr].q1=x1*d,D[Nr].q2=x2*(A/d);
                    D[++Nr].p1=A/d,D[Nr].p2=d,D[Nr].q1=-x2*A/d,D[Nr].q2=-x1*d;
                    D[++Nr].p1=-A/d,D[Nr].p2=-d,D[Nr].q1=x2*A/d,D[Nr].q2=x1*d;
                }


                if(valid(x1,A/d,x2,d)){
                    D[++Nr].p1=d,D[Nr].p2=A/d,D[Nr].q1=-x2*d,D[Nr].q2=-x1*(A/d);
                    D[++Nr].p1=-d,D[Nr].p2=-A/d,D[Nr].q1=x2*d,D[Nr].q2=x1*(A/d);
                    D[++Nr].p1=A/d,D[Nr].p2=d,D[Nr].q1=-x1*A/d,D[Nr].q2=-x2*d;
                    D[++Nr].p1=-A/d,D[Nr].p2=-d,D[Nr].q1=x1*A/d,D[Nr].q2=x2*d;
                }


        }

    N=Nr;
    for(int i=1;i<=N;i++){
        int j=i;
        while(j/2 && comp(j,j/2)>0){
            swap(j,j/2);
            j>>=1;
        }
    }

    int Nh=N;
    while(Nh>1){
        swap(Nh,1);
        --Nh;

        int i=1,j;
        while(1){
            j=2*i;
            if(j>Nh) break;
            if(j+1<=Nh && comp(j+1,j)>0) ++j;
            if(comp(j,j/2)<0) break;
            swap(j,j/2);
            i=j;
        }
    }

    int cnt=0;
    int i;
    for(i=1;i<=N&&cnt<X;i++)
        if(comp(i,i-1)!=0)
            ++cnt;
    --i;


    if(cnt<X)
        fprintf(fout,"-1");
    else{
    fprintf(fout,"(");
    if(D[i].p1==1)
        fprintf(fout,"x");
    else
        if(D[i].p1==-1)
            fprintf(fout,"-x");
        else
            fprintf(fout,"%dx",D[i].p1);
    if(D[i].q1<0)
        fprintf(fout,"%d)(",D[i].q1);
    else
        fprintf(fout,"+%d)(",D[i].q1);
    if(D[i].p2==1)
        fprintf(fout,"x");
    else
        if(D[i].p2==-1)
            fprintf(fout,"-x");
        else
            fprintf(fout,"%dx",D[i].p2);
    if(D[i].q2<0)
        fprintf(fout,"%d)\n",D[i].q2);
    else
        fprintf(fout,"+%d)\n",D[i].q2);

    }
    fclose(fin);
    fclose(fout);
    return 0;

}