Cod sursa(job #245935)

Utilizator eugen.nodeaEugen Nodea eugen.nodea Data 19 ianuarie 2009 14:25:10
Problema Ecuatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
long A,B,C,K,k=0;
struct ecuatie{
  long P1,P2,Q1,Q2;
} E[50000],aux;
void quick(long st, long dr)
{
  long i=st,j=dr;
  ecuatie p=E[(st+dr)/2],aux;
  if (dr<=st) return;
  while (i<=j){
    while (E[i].P1<p.P1) i++;
    while (p.P1<E[j].P1) j--;
    if (i<=j) {
    aux=E[i];E[i]=E[j];E[j]=aux;
    i++; j--;
    }
  }
  if (st<j) quick(st,j);
  if (i<dr) quick(i,dr);
}
int main(){
  double q1,q2,x1,x2;
  long p1,p2,d,i,ok;
  freopen("ecuatie.in", "r", stdin);
  freopen("ecuatie.out", "w", stdout);
  scanf("%ld %ld %ld %ld",&A,&B,&C,&K);
  x1=(-B-sqrt(B*B-4*A*C))/(2*A);
  x2=(-B+sqrt(B*B-4*A*C))/(2*A);
  for (d=1;d<=sqrt(abs(A));d++)
     if (A%d==0){
	    p1=d; p2=A/d;
	    q1=-x1*d; q2=-x2*(A/d);
	    if (q1==long(q1) && q2==long(q2)) {
		k++;
		E[k].P1=p1;E[k].P2=p2;E[k].Q1=long(q1);E[k].Q2=long(q2);
		k++;
		E[k].P1=-p1;E[k].P2=-p2;E[k].Q1=long(-q1);E[k].Q2=long(-q2);
		}
	    q1=-x2*d; q2=-x1*(A/d);
	    if (q1==long(q1) && q2==long(q2)) {
		k++;
		E[k].P1=p1;E[k].P2=p2;E[k].Q1=long(q1);E[k].Q2=long(q2);
		k++;
		E[k].P1=-p1;E[k].P2=-p2;E[k].Q1=long(-q1);E[k].Q2=long(-q2);
		}
  }
   d=A;
   p1=d; p2=A/d;
   q1=-x1*d; q2=-x2*(A/d);
   if (q1==long(q1) && q2==long(q2)) {
		k++;
		E[k].P1=p1;E[k].P2=p2;E[k].Q1=long(q1);E[k].Q2=long(q2);
		k++;
		E[k].P1=-p1;E[k].P2=-p2;E[k].Q1=long(-q1);E[k].Q2=long(-q2);
		}
   q1=-x2*d; q2=-x1*(A/d);
   if (q1==long(q1) && q2==long(q2)) {
		k++;
		E[k].P1=p1;E[k].P2=p2;E[k].Q1=long(q1);E[k].Q2=long(q2);
		k++;
		E[k].P1=-p1;E[k].P2=-p2;E[k].Q1=long(-q1);E[k].Q2=long(-q2);
		}
  if (K>k) { printf("-1"); return 0;}
  quick(1,k);
  p1=k;
  do{
     ok=1;
     for (i=1;i<p1;i++)
       if (E[i].P1==E[i+1].P1 && E[i].Q1>E[i+1].Q1) {
	aux=E[i];E[i]=E[i+1];E[i+1]=aux; ok=0; p2=i;
       }
      p1=p2;
  }while (!ok);
  i=1;
  while (K>1 && i<=k){
    while (E[i].P1==E[i+1].P1 && E[i].P2==E[i+1].P2 && E[i].Q1==E[i+1].Q1 && E[i].Q2==E[i+1].Q2) i++;
    K--; i++;
  }
  printf("(");
  if (E[i].P1==1) printf("x");
    else if (E[i].P1==-1) printf("-x");
		     else printf("%ldx",E[i].P1);
  if (E[i].Q1>=0) printf("+%ld",E[i].Q1);
	    else  printf("-%ld",-1*E[i].Q1);
  printf(")(");
  if (E[i].P2==1) printf("x");
    else if (E[i].P2==-1) printf("-x");
		     else printf("%ldx",E[i].P2);
  if (E[i].Q2>=0) printf("+%ld",E[i].Q2);
	    else  printf("-%ld",-1*E[i].Q2);
  printf(")");
  return 0;
}