Cod sursa(job #530827)

Utilizator superman13Stefan Maimescu superman13 Data 8 februarie 2011 15:29:01
Problema Loto Scor 95
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.75 kb
program test;
type el=record
     sum,v1,v2,v3:longint;
     end;
    ta = array [1..1000000] of el;
    ta2= array [1..100] of longint;
var
    w,st,dr,q,n,i,j,k,ss,dim:longint;
    a:ta;
    s:ta2;


function impartire(st,dr:longint):longint;
var x:longint;
    fl:boolean;
    aux:el;
begin
x:=a[st].sum;
i:=st-1;
j:=dr+1;
fl:=true;
while fl do
      begin
      repeat
      j:=j-1;
      until a[j].sum<=x;
      repeat
      i:=i+1;
      until a[i].sum>=x;
      if i<j then
         begin
         aux:=a[i];
         a[i]:=a[j];
         a[j]:=aux;
         end
             else
         begin
         impartire:=j;
         exit;
         end;
      end;
end;





procedure quick(st,dr:longint);
begin
if st<dr then
   begin
   q:=impartire(st,dr);
   quick(st,q);
   quick(q+1,dr);
   end;
end;


begin {pp}
assign(input,'loto.in');reset(input);
readln(n,ss);
for i:=1 to n do
    read(s[i]);
close(input);
dim:=0;
for i:=1 to n do
    for j:=i to n do
        for k:=j to n do
            begin
            inc(dim);
            a[dim].sum:=s[i]+s[j]+s[k];
            a[dim].v1:=s[i];
            a[dim].v2:=s[j];
            a[dim].v3:=s[k];
            end;
quick(1,dim);
for i:=1 to dim do
    begin
    st:=0;
    dr:=dim;
    w:=a[i].sum;
    while st<dr do
          begin
          q:=(st+dr) div 2;
          if a[q].sum+w=ss then
             begin
             assign(output, 'loto.out');rewrite(output);
             write(a[i].v1,' ',a[i].v2,' ',a[i].v3,' ');
             write(a[q].v1,' ',a[q].v2,' ',a[q].v3);
             close(output);
             exit;
             end;
          if a[q].sum+w<ss then st:=q+1
                           else dr:=q;
          end;
    end;
assign(output, 'loto.out');rewrite(output);
write(output, '-1');
close(output);
end.