Cod sursa(job #252877)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 5 februarie 2009 00:10:33
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.54 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;
long double delta,x1,x2;
struct produs{int p1,p2,q1,q2;};
produs D[60000];

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 conv(long double x){
    int semn=1;
    if(x<0)
        semn=-1;
    if( (int) ((long double) x*10000) % 10000 == 9999 )
        ++x;
    return (int) x;
}

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

    D[0].p1=D[0].p2=D[0].q1=D[0].q2=0;

    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=-conv(x1*d),D[Nr].q2=-conv(x2*(A/d));
                    D[++Nr].p1=-d,D[Nr].p2=-A/d,D[Nr].q1=conv(x1*d),D[Nr].q2=conv(x2*(A/d));
                    D[++Nr].p1=A/d,D[Nr].p2=d,D[Nr].q1=-conv(x2*A/d),D[Nr].q2=-conv(x1*d);
                    D[++Nr].p1=-A/d,D[Nr].p2=-d,D[Nr].q1=conv(x2*A/d),D[Nr].q2=conv(x1*d);
                }


                if(valid(x1,A/d,x2,d)){
                    D[++Nr].p1=d,D[Nr].p2=A/d,D[Nr].q1=-conv(x2*d),D[Nr].q2=-conv(x1*(A/d));
                    D[++Nr].p1=-d,D[Nr].p2=-A/d,D[Nr].q1=conv(x2*d),D[Nr].q2=conv(x1*(A/d));
                    D[++Nr].p1=A/d,D[Nr].p2=d,D[Nr].q1=-conv(x1*A/d),D[Nr].q2=-conv(x2*d);
                    D[++Nr].p1=-A/d,D[Nr].p2=-d,D[Nr].q1=conv(x1*A/d),D[Nr].q2=conv(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{
        /*if(D[i].p1*D[i].p2==A&&D[i].p1*D[i].q2+D[i].p2*D[i].q1==B&&D[i].q1*D[i].q2==C)
            while(1);*/
    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;

}