Cod sursa(job #168161)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 30 martie 2008 20:24:46
Problema Loto Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.83 kb
var a,o:array[1..8000000] of longint;
    n,i,j,k,t,op,s,q:longint;
    b,d,w,oo:array[1..8000000] of int64;
    c:array[1..200] of longint;
    f,g:text;
    ok:boolean;

procedure inter(st,dr,mij:longint);
 var i,j,k,t:longint;
 begin
  for t:=st to dr do begin
   o[t]:=a[t];
   oo[t]:=d[t];
  end;
  i:=st; k:=st; j:=mij+1;
  while (i<=mij) and (j<=dr) do begin
   if o[i]>o[j] then begin
    a[k]:=o[i];
    d[k]:=oo[i];
    inc(i);
   end
   else begin
    a[k]:=o[j];
    d[k]:=oo[j];
    inc(j);
   end;
   inc(k);
  end;
  for t:=i to mij do begin
   a[t+k-i]:=o[t];
   d[t+k-i]:=oo[t];
  end;
  for t:=j to dr do begin
   a[t+k-j]:=o[t];
   d[t+k-j]:=oo[t];
  end;
 end;

procedure merge(st,dr:longint);
 var mij:longint;
 begin
  if st<dr then begin
   mij:=(st+dr) shr 1;
   merge(st,mij);
   merge(mij+1,dr);
   inter(st,dr,mij);
  end;
 end;

function cauta(x,st,dr:longint):longint;
 var mij:longint;
 begin
  if st>dr then cauta:=0
  else
   begin
    mij:=(st+dr)div 2;
    if a[mij]=x then
     cauta:=mij
    else
     if a[mij]<x then
      cauta:=cauta(x,st,mij-1)
     else
      cauta:=cauta(x,mij+1,dr);
   end;
 end;
begin
 assign(f,'loto.in'); reset(f);
 assign(g,'loto.out'); rewrite(g);
 read(f,n,s);
 for i:=1 to n do
  read(f,c[i]);
 for i:=1 to n do
  for j:=i to n do
   for k:=j to n do begin
    inc(op);
    a[op]:=c[i]+c[j]+c[k];
    d[op]:=i*1000000+j*1000+k;
   end;
 merge(1,op);
 i:=1;
 ok:=false;
 for i:=1 to op do begin
  q:=cauta(s-a[i],1,op);
  if q<>0 then begin
   writeln(g,c[d[i] div 1000000],' ',c[(d[i] mod 1000000) div 1000],' ',c[d[i] mod 1000],' ',c[d[q] div 1000000],' ',c[(d[q] mod 1000000) div 1000],' ',c[d[q] mod 1000]);
   ok:=true;
   break;
  end;
 end;
 if ok=false then
  writeln(g,'-1');
 close(f); close(g);
end.