Cod sursa(job #904491)

Utilizator ThorophRadu Alexandru Thoroph Data 4 martie 2013 15:16:34
Problema Loto Scor 5
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.44 kb
program loto;

type
  structura = record
    sum, n1, n2, n3: longint;
  end;

var
  n, poz: byte;
  s: longint;
  v: array[1..105]of longint;
  ss: array[1..1000005]of structura;

procedure readdata;
var
  f: text;
  i: byte;
begin
  assign(f, 'loto.in');
  reset(f);
  readln(f, n, s);
  for i := 1 to n do
    read(f, v[i]);
  close(f);
end;

procedure quicksort(left, right: longint);
var
  i, j: longint;
  pivot, tmp: structura;
begin
  i := left;
  j := right;
  pivot := ss[(left+right) div 2];
  repeat
    while pivot.sum > ss[i].sum do inc(i);
    while pivot.sum < ss[j].sum do dec(j);
    if i <= j then
    begin
      tmp := ss[i];
      ss[i] := ss[j];
      ss[j] := tmp;
      dec(j);
      inc(i);
    end;
  until i > j;
  if left < j then quicksort(left, j);
  if i < right then quicksort(i, right);
end;

procedure writenosolution;
var
  f: text;
begin
  assign(f, 'loto.out');
  rewrite(f);
  writeln(f, -1);
  close(f);
end;

function cautare_binara(n: byte; suma: longint): integer;
var
  primul, ultimul, mijloc: byte;
begin
  if (n=1) and (suma=ss[1].sum) then
  begin
    cautare_binara := 0;
    Exit;
  end;

  primul := 1;
  ultimul := n;

  if ss[ultimul].sum < suma then
  begin
    cautare_binara := -1;
    Exit;
  end;

  while primul <= ultimul do
  begin
    mijloc := (primul + ultimul) shr 1;
    if ss[mijloc].sum = suma then
    begin
      cautare_binara := mijloc;
      Exit;
    end;

    if ss[mijloc].sum < suma then
      primul := mijloc + 1
    else
      ultimul := mijloc - 1;
  end;
  cautare_binara := -1;
end;

procedure solve;
var
  i, j, ci: byte;
  k: longint;
  f: text;
begin
  for i := 1 to n do
    for j := i to n do
      for k := j to n do
      begin
        inc(poz);
        ss[poz].sum := v[i] + v[j] + v[k];
        ss[poz].n1  := v[i];
        ss[poz].n2  := v[j];
        ss[poz].n3  := v[k];
      end;

  quicksort(1, poz);

  if ss[poz].sum * 2 < s then
  begin
    writenosolution;
    halt;
  end;

  for i := 1 to poz do
  begin
    k := cautare_binara(n, s-ss[i].sum);
    if k <> -1 then
      begin
        Assign(f, 'loto.out');
        Rewrite(f);
        WriteLn(f, ss[i].n1, ' ', ss[i].n2, ' ', ss[i].n3, ' ', ss[k].n1, ' ', ss[k].n2, ' ', ss[k].n3);
        Close(f);
        Halt;
      end
    else
      WriteNoSolution;
  end;
end;

begin
  readdata;
  solve;
end.