Cod sursa(job #239428)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 4 ianuarie 2009 19:21:54
Problema Ecuatie Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.49 kb
type sol=record
     p1,q1,p2,q2:int64;
     end;

var v,so:array[1..100000] of sol;
    f,g:text;
    nr,i,k:longint;
    delta,a,b,c,x1,x2:int64;
    exista:boolean;

procedure ins(d:longint);
 begin
  inc(nr);
  v[nr].p1:=d;
  v[nr].q1:=-x1*d;
  v[nr].p2:=a div d;
  v[nr].q2:=-x2*(a div d);
  if (v[nr].q1 mod (2*a)<>0) or (v[nr].q2 mod (2*a)<>0) then
   dec(nr)
  else begin
   v[nr].q1:=v[nr].q1 div (2*a);
   v[nr].q2:=v[nr].q2 div (2*a);
  end;
  inc(nr);
  v[nr].p1:=d;
  v[nr].q1:=-x2*d;
  v[nr].p2:=a div d;
  v[nr].q2:=-x1*(a div d);
  if (v[nr].q1 mod (2*a)<>0) or (v[nr].q2 mod (2*a)<>0) then
   dec(nr)
  else begin
   v[nr].q1:=v[nr].q1 div (2*a);
   v[nr].q2:=v[nr].q2 div (2*a);
  end;
 end;

function cmp(x,y:sol):boolean;
 begin
  if x.p1<y.p1 then cmp:=true
  else
   if (x.p1=y.p1) and (x.q1<y.q1) then cmp:=true
   else cmp:=false;
 end;

procedure qsort(l,r:longint);
 var i,j:longint;
     x,y:sol;
 begin
  i:=l; j:=r; x:=v[random(r-l+1)+l];
  repeat
    while cmp(v[i],x) do i:=i+1;
    while cmp(x,v[j]) do j:=j-1;
    if i<=j then begin
      y:=v[i]; v[i]:=v[j]; v[j]:=y;
      i:=i+1; j:=j-1;
    end;
  until i>j;
  if l<j then qsort(l,j);
  if i<r then qsort(i,r);
 end;

procedure er;
 var i,q:longint;
 begin
  q:=nr; nr:=0;
  for i:=1 to q-1 do
   if cmp(v[i],v[i+1]) then begin
    inc(nr);
    so[nr]:=v[i];
   end;
  inc(nr);
  so[nr]:=v[q];
 end;

procedure afis(x:sol);
 var q1,q2,p1,p2:longint;
 begin
  p1:=x.p1; q1:=x.q1; p2:=x.p2; q2:=x.q2;
  write(g,'(');
  if (p1<>1) and (p1<>-1) then write(g,p1);
  if p1=-1 then write(g,'-'); write(g,'x');
  if q1<0 then write(g,q1) else write(g,'+',q1);
  write(g,')');
  write(g,'(');
  if (p2<>1) and (p2<>-1) then write(g,p2);
  if p2=-1 then write(g,'-'); write(g,'x');
  if q2<0 then write(g,q2) else write(g,'+',q2);
  write(g,')');
  writeln(g);
 end;

begin
 assign(f,'ecuatie.in'); reset(f);
 assign(g,'ecuatie.out'); rewrite(g);
 read(f,a,b,c,k);
 delta:=b*b-4*a*c;
 exista:=false;
 if (delta>=0) and (trunc(sqrt(delta))=sqrt(delta)) then
  exista:=true;
 if exista then begin
  x1:=(-b-trunc(sqrt(delta)));
  x2:=(-b+trunc(sqrt(delta)));
  nr:=0;
  for i:=1 to trunc(sqrt(abs(a))) do
   if a mod i=0 then begin
    ins(i);
    ins(-i);
    ins(a div i);
    ins(-a div i);
   end;
  randomize;
  qsort(1,nr);
  er;
 end;
 if nr<k then
  exista:=false;
 if exista then
  afis(so[k])
 else
  writeln(g,-1);
 close(f); close(g);
end.