Cod sursa(job #171707)

Utilizator DonPushmeMilitaru Adrian DonPushme Data 4 aprilie 2008 21:18:57
Problema Loto Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.99 kb
type vector=array[1..1000000] of longint;

var suma,x:vector;
     n,m,i,j,k,s,ic,sf,mij:longint;
     ok:boolean;

procedure Sort(var a:vector;l, r: longint);
var
  i, j, x, y: longint;
begin
  i := l; j := r; x := a[(l+r) DIV 2];
  repeat
    while a[i] < x do i := i + 1;
    while x < a[j] do j := j - 1;
    if i <= j then
    begin
      y := a[i]; a[i] := a[j]; a[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(a,l, j);
  if i < r then Sort(a,i, r);
end;


procedure afisare(p:longint);
var i,j,k,e:longint;
Begin
e:=0;
For i:=1 to n do
 For j:=1 to n do
  For k:=1 to n do
   If (x[i]+x[j]+x[k]=suma[p]) and (e=0) then Begin
                                               Write(x[i],' ',x[j],' ',x[k],' ');
                                               inc(e);
                                               break;
                                              end;
end;

Begin
Assign(input,'loto.in');Reset(input);
Assign(output,'loto.out');Rewrite(output);
Readln(n,s);

For i:=1 to n do 
	Read(x[i]);
m:=0;
For i:=1 to n do
 For j:=1 to n do
  For k:=1 to n  do
   Begin
    m:=m+1;
    suma[m]:=x[i]+x[j]+x[k];
   end;
Sort(suma,1,m);
ok:=false;
ic:=1;
sf:=m;
 While ic<=sf do
  Begin
   mij:=(ic+sf) div 2;
   If suma[ic]+suma[sf]=S then Begin
                                ok:=true;
                                afisare(ic);
                                afisare(sf);
                                ic:=sf+1;
                               end
                           else Begin
                                 While (suma[ic]+suma[sf]>S) and (sf>=1) do dec(sf);
                                 While (suma[ic]+suma[sf]<S) and (ic<=m) do inc(ic);
                                end;
                                {If suma[ic]+suma[sf]>S then sf:=mij-1
                                                       else ic:=mij+1;}
   end;
If not ok then Write(-1);
Close(input);
Close(output);
end.