Cod sursa(job #432354)

Utilizator C0Mr4d3yonootz321 C0Mr4d3 Data 2 aprilie 2010 11:40:59
Problema Loto Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.67 kb
type vector=array[1..1000000] of longint;
var  suma,x:vector;
     n,m,i,j,k,s,st,dr,mij:longint;
     ok:boolean;

procedure sortare(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
      inc(i);
    while x<a[j] do
      dec(j);
    if i<=j then
      begin
        y:=a[i];
        a[i]:=a[j];
        a[j]:=y;
        inc(i);
        dec(j);
      end;
  until i>j;
  if l<j then
    sortare(a,l, j);
  if i<r then
    sortare(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(output,x[i],' ',x[j],' ',x[k],' ');
            exit;
          end;
end;

begin
  assign(input,'loto.in');
  reset(input);
  readln(input,n,s);
  for i:=1 to n do
    read(input,x[i]);
  close(input);
  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;
  sortare(suma,1,m);
  ok:=false;
  st:=1;
  dr:=m;
  assign(output,'loto.out');
  rewrite(output);
  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(output,-1);
  close(output);
end.