Cod sursa(job #609974)

Utilizator danalex97Dan H Alexandru danalex97 Data 24 august 2011 10:20:42
Problema Loto Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.84 kb
var n,i,j,k,s,nr,n1,n2,ind:longint;
    a:array[1..5000] of longint;
    b:array[1..100] of longint;
    c:array[1..5000,1..3] of integer;
    f,g:text;
    ok:boolean;

function pozitionare(st,dr:integer):integer;
var xst,xdr,aux:integer;
begin
  xst:=0;
  xdr:=-1;
  while st<dr do
    if a[st]<a[dr] then
      begin
        st:=st+xst;
        dr:=dr+xdr;
      end
    else
      begin
        aux:=a[st];
        a[st]:=a[dr];
        a[dr]:=aux;
        aux:=c[st,1];
        c[st,1]:=c[dr,1];
        c[dr,1]:=aux;
        aux:=c[st,2];
        c[st,2]:=c[dr,2];
        c[dr,2]:=aux;
        aux:=c[st,3];
        c[st,3]:=c[dr,3];
        c[dr,3]:=aux;
        xst:=1-xst;
        xdr:=-1-xdr;
        st:=st+xst;
        dr:=dr+xdr;
      end;
  pozitionare:=st;
end;

procedure quick(st,dr:integer);
var p:integer;
begin
  p:=pozitionare(st,dr);
  if st<p-1 then quick(st,p-1);
  if p+1<dr then quick(p+1,dr);
end;

procedure cautbin(st,dr:integer);
var mij:longint;
begin
mij:=(st+dr) div 2;
if st<dr then
if a[mij]=n2 then begin ok:=true;ind:=mij; end
  else
if a[mij]<n2 then cautbin(mij+1,dr)
  else
cautbin(st,mij-1);
if dr<st then ok:=false;
end;

begin
  assign(f,'loto.in');reset(f);
  assign(g,'loto.out');rewrite(g);
  read(f,n,s);
  for i:=1 to n do
    read(f,b[i]);
  nr:=0;
  for i:=1 to n do
    for j:=1 to n do
      for k:=1 to n do
        begin
          inc(nr);
          a[nr]:=b[i]+b[j]+b[k];
          c[nr,1]:=b[i];
          c[nr,2]:=b[j];
          c[nr,3]:=b[k];
        end;
  quick(1,nr);
  ok:=false;
  for i:=1 to nr do
    begin
      n1:=a[i];
      n2:=s-n1;
      cautbin(1,nr);
    end;
  if ok then
    writeln(g,c[i,1],' ',c[i,2],' ',c[i,3],' ',c[ind,1],' ',c[ind,2],' ',c[ind,3])
  else
    writeln(g,'-1');
  close(f);
  close(g);
end.