Cod sursa(job #26152)

Utilizator hitmannCiocas Radu hitmann Data 5 martie 2007 11:48:27
Problema Loto Scor 5
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.01 kb
program loto;
type el=record
     x1,x2,x3:longint;
     end;
var su:array[1..1000000]of el;
    v:array[1..100]of longint;
    s:int64;
    n,i,j,k,l,m,e:longint;
    g:text;
    ok:boolean;
procedure citire;
var f:text;
begin
assign(f,'loto.in');reset(f);
read(f,n,s);
for i:=1 to n do read(f,v[i]);
close(f);
end;
procedure quicksort(s,d:int64);
var i,j:int64;
    aux:el;
    e:int64;
begin
i:=s;
j:=d;
e:=su[(s+d)div 2].x1+su[(s+d)div 2].x2+su[(s+d)div 2].x3;
repeat
while su[i].x1+su[i].x2+su[i].x3<e do inc(i);
while su[j].x1+su[j].x2+su[j].x3>e do dec(j);
if i<=j then
 begin
 aux:=su[i];
 su[i]:=su[j];
 su[j]:=aux;
 inc(i);
 dec(j);
 end;
until i>j;
if s<j then quicksort(s,j);
if d>i then quicksort(i,d);
end;
function suma(i:longint):int64;
begin
suma:=v[su[i].x1]+v[su[i].x2]+v[su[i].x3];
end;
function search(val: int64): int64;
var
  i, step: int64;
begin
  step := 1;
  while (step < l) do step := step shl 1;
  i := 0;
  while (step <> 0) do begin
    if (i + step < l) and (suma(i+step) <= val) then
      i := i + step;
    step := step shr 1;
  end;
  search := i;
end;
function cauta(val:int64;s,d:longint):int64;
var m:longint;
begin
ok:=true;
 while (s<=d)and ok do
  begin
  m:=(s+d)div 2;
  if val >suma(m) then s:=m+1
                  else if val<suma(m) then d:=m-1
                                      else begin cauta:=m; ok:=false; end;
  end;
if val<>suma(m) then cauta:=0;
end;
begin {pp}
citire;
l:=0;
for i:=1 to n do
 for j:=1 to n do
  for k:=1 to n do
    begin
    inc(l);
    su[l].x1:=i;
    su[l].x2:=j;
    su[l].x3:=k;
    end;
quicksort(1,l);
assign(g,'loto.out'); rewrite(g);
ok:=true;
i:=1;
while (i<=l)and ok do
begin
 if suma(i)<=s then
 begin
 j:=cauta(s-suma(i),1,l);
 if j<>0 then
         begin
         ok:=false;
         write(g,v[su[i].x1],' ',v[su[i].x2],' ',v[su[i].x3],' ',v[su[j].x1],' ',v[su[j].x2],' ',v[su[j].x3]);

         end;
  end;
 inc(i);
 end;
if ok then write(g,-1);
close(g);
end.