Cod sursa(job #1152550)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 24 martie 2014 19:52:35
Problema Loto Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.16 kb
Program a1;
type numar = record
        sum:longint;
        nr1:longint;
        nr2:longint;
        nr3:longint;
end;
var i,s,p,val:longint;
    n,j,k:integer;
    v:array[1..200] of longint;
    a:array[1..5000001] of numar;
    aux:numar;
    input,output:text;
procedure quicksort(left:longint;right:longint);
var i,j,pivot:longint;
begin
i:=left;
j:=right;
pivot:=a[(i+(j-i) div 2)].sum;
while i<= j do
   begin
   while a[i].sum<pivot do inc(i);
   while a[j].sum>pivot do dec(j);
   if i<=j then begin
        aux.sum:=a[i].sum;
        aux.nr1:=a[i].nr1;
        aux.nr2:=a[i].nr2;
        aux.nr3:=a[i].nr3;
        a[i].sum:=a[j].sum;
        a[i].nr1:=a[j].nr1;
        a[i].nr2:=a[j].nr2;
        a[i].nr3:=a[j].nr3;
        a[j].sum:=aux.sum;
        a[j].nr1:=aux.nr1;
        a[j].nr3:=aux.nr3;
        a[j].nr2:=aux.nr2;
        inc(i);
        dec(j);
       end;
   end;
   if left < j then quicksort(left,j);
   if right > i then quicksort(i,right);
end;
function bin_search(left:longint;right:longint;val:longint):longint;
var mid:longint;
    gasit:boolean;
begin
gasit:=false;
while left <= right do begin
mid:=left+(right-left) div 2;
if a[mid].sum = val then begin gasit:=true;bin_search:=mid;exit;end;
if val > a[mid].sum then left:=mid+1
else right:=mid-1;
end;
if not gasit then bin_search:=0;
end;
begin
assign(input,'loto.in');
assign(output,'loto.out');
reset(input);
rewrite(output);
readln(input,n,s);
p:=1;
for i:=1 to n do read(input,v[i]);
for i:=1 to n do
    for j:=i to n do
       for k:=j to n do
          begin
              a[p].sum:=v[i]+v[k]+v[j];
              a[p].nr1:=v[i];
              a[p].nr2:=v[j];
              a[p].nr3:=v[k];
              inc(p);
          end;
quicksort(1,p-1);
for i:=1 to p do
   begin
        val:=bin_search(1,p-1,s-a[i].sum);
        if(val<>0) then begin
          write(output,a[i].nr1,' ',a[i].nr2,' ',a[i].nr3,' ');
          write(output,a[val].nr1,' ',a[val].nr2,' ',a[val].nr3);
          close(input);
          close(output);
          exit;
          end;
   end;
   write(output,'-1');
   close(input);
   close(output);
   end.