Cod sursa(job #215598)

Utilizator FllorynMitu Florin Danut Flloryn Data 19 octombrie 2008 17:16:43
Problema Loto Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.64 kb
 Type list=array[1..1000000] of longint;
 var f:text;
     suma,x:list;
     n,m,i,j,k,s,st,dr,mij:longint;
     ok:boolean;

 procedure Sort(var a:list; 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,q:longint;
  Begin
  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]) then begin
                    Write(f,x[i],' ',x[j],' ',x[k],' ');
                     exit;
                      end;
  end;

  begin
  assign(f,'loto.in');reset(f);
  readln(f,n,s);
  for i:=1 to n do read(f,x[i]);  close(f);
  m:=0;
  for i:=1 to n do
   for j:=1 to n do
      for k:=1 to n do
     begin
      inc(m);
      suma[m]:=x[i]+x[j]+x[k];
     end;

  Sort(suma,1,m);
  ok:=false;
  st:=1; dr:=m;

  assign(f,'loto.out');rewrite(f);
  while st<=dr do
    begin
      mij:=(st+dr) div 2;
      if suma[st]+suma[dr]=s then begin
                                     ok:=true;
                                     afisare(st);
                                     afisare(dr);
                                     st:=dr+1;
                                  end
  else
    begin
    while (suma[st]+suma[dr]>s) and (dr>=1) do dec(dr);
    while (suma[st]+suma[dr]<s) and (st<=m) do inc(st);
    end;
  end;
  if not ok then write(f,-1);
  close(f);
 end.