Логично.А я думаю, что невозможно больше 16. Об этом, кстати, S_lip писал.
Т.е. при заданных ограничениях первые 16 упорядоченного массива ВСЕГДА будут содержать минимум одну искомую группу.
Впрочем, возможно, я и ошибаюся. Просто я не могу придумать алгоритм, который смог бы сгенерировать последовательность, не содержащую искомых групп, длиной больше 15.

сейчас попробуем.

выбрать не получилось.

видимо, можно доказать, что максимум - 14. примерно понимаю, как, могу довести до конца.

но, возвращаясь к оценкам - 3^N, где N = скольки? Тебе ведь нужно перебрать все возможные выборки из данных 200 чисел, т.к. нас интересует минимум. мне кажется, заоптимизировать это настолько, чтоб оно работало на всех тестах в пределах секунды - нереально.

Жду с интересом.
PS.: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384. 15 штукНе нужно. Сортируем по возрастанию и перебираем не более 16 первых.Ну, можно начать с нескольких эвристик. Мне кажется, "тяжелые" для перебора случаи должны легко поддаваться жадному алгоритму.

Ну 15. Какая разница.



Это не обязательно правильно.



Можешь написать и попросить ОП проверить на сайте.

Michael_Rybak, спасибо за пример.
Вот исправленный код:

const
  MaxCount=200;
  MaxSum=100000;
type
  posanddif=record
    c,d:longint;
  end;
var
  a:array [1..MaxCount] of integer;
  n:byte;
  u,d:array [1..(MaxSum div 2)] of longint;
  udn:longint;
  b:array [0..(MaxSum div 2)] of longint;
  pad:array [1..(MaxSum div 2)] of posanddif;
  pn:longint;
  f:text;
  i,j:longint;

procedure ProcessUD(uu,dd:longint);
var
  ii:longint;
begin
  if dd<=(MaxSum div 2) then begin
    if b[dd-uu]>0 then begin
      if u[b[dd-uu]]>uu then begin
        ii:=1;
        while (ii<=pn) and (pad[ii].c<>b[dd-uu]) do inc(ii);
        if ii>pn then begin
          inc(pn);
          pad[pn].c:=b[dd-uu];
          pad[pn].d:=u[b[dd-uu]]-uu;
        end else if pad[ii].d>u[b[dd-uu]]-uu then
          pad[ii].d:=u[b[dd-uu]]-uu;
      end;
    end else begin
      inc(udn);
      u[udn]:=uu;
      d[udn]:=dd;
      b[dd-uu]:=udn;
    end;
  end;
end;

begin
  assign(f,'file.in');
  reset(f);
  readln(f,n);
  for i:= 1 to n do
    readln(f,a[i]);
  close(f);

  for i:= 0 to (MaxSum div 2) do b[i]:=0;
  udn:=1;
  i:=1;
  u[1]:=0;
  d[1]:=a[1];
  b[a[1]]:=a[1];

  for i:= 2 to n do begin

    pn:=0;
    j:=udn;

    ProcessUD(0,a[i]);

    for j:= 1 to j do begin
      ProcessUD(u[j],d[j]+a[i]);
      if u[j]+a[i]<d[j] then ProcessUD(u[j]+a[i],d[j])
      else ProcessUD(d[j],u[j]+a[i]);
    end;

    for j:= 1 to pn do begin
      dec(u[pad[j].c],pad[j].d);
      dec(d[pad[j].c],pad[j].d);
    end;

  end;
  writeln(u[b[0]]); //ответ
end.

Главное отличие - обходим все элементы, а также убрана медленная проверка в конце главного цикла и добавлен массив pad, который содержит позицию "с" и разницу "d" тех элементов, для которых мы нашли замену.
Этот пример также навел на мысль, что максимальное количество перебираемых чисел будет не 15 и не 16, а... 7502 (1 15000 15002 15004 ... 29998 29999). Поэтому нужно перебирать все n. Однако прога не справилась с примером из 200 чисел (1 200 202 204 ... 594 595). udn выходит за пределы 50000. Ошибка 201. Я потратил достаточно много времени, чтобы найти, где промах, но безуспешно.
Этот пример в 200 чисел прикреплен.

Сообщение отредактировано: S_lip - 1.01.2008 1:00

на самом деле 15.

1 15000 15002 15004 ... 29998 29999- если ты имел ввиду все четные, начиная с 15000, то сразу же получится 15000+15006 = 15002+15004.

ночью посмотрю, где ошибка.

15000+15006 = 15002+15004 = 30006
1+29998 = 29999

А, теперь я понял, к чему этот пример был.

Отличная мысль.

andriano, видишь, этот тест показывает, что нельзя оставлять наименьших 16.

Спасибо большое всем, кто потратил свое время читая это все и пытался помочь...
Я нашел решение:

const
  MaxCount=200;
  MaxSum=100000;
type
  posanddif=record
    c,u:longint;
  end;
var
  a:array [1..MaxCount] of integer;
  n:byte;
  u,d,b:array [0..(MaxSum div 2)] of longint;
  udn:longint;
  pad:array [1..(MaxSum div 2)] of posanddif;
  pn:longint;
  f:text;
  i,j:longint;

procedure ProcessUD(uu,dd:longint);
begin
  if dd<=(MaxSum div 2) then begin
    if b[dd-uu]>0 then begin
      if u[b[dd-uu]]>uu then begin
        inc(pn);
        pad[pn].c:=b[dd-uu];
        pad[pn].u:=uu;
      end;
    end else begin
      inc(udn);
      u[udn]:=uu;
      d[udn]:=dd;
      b[dd-uu]:=udn;
    end;
  end;
end;

begin
  assign(f,'file.in');
  reset(f);
  readln(f,n);
  for i:= 1 to n do
    readln(f,a[i]);
  close(f);

  for i:= 0 to (MaxSum div 2) do b[i]:=0;
  udn:=0;
  i:=1;
  u[0]:=0;
  d[0]:=a[1];
  b[a[1]]:=a[1];

  for i:= 2 to n do begin

    pn:=0;
    j:=udn;

    ProcessUD(0,a[i]);

    for j:= 0 to j do begin
      ProcessUD(u[j],d[j]+a[i]);
      if u[j]+a[i]<d[j] then ProcessUD(u[j]+a[i],d[j])
      else ProcessUD(d[j],u[j]+a[i]);
    end;

    for j:= 1 to pn do begin
      if pad[j].u<u[pad[j].c] then begin
        dec(d[pad[j].c],u[pad[j].c]-pad[j].u);
        u[pad[j].c]:=pad[j].u;
      end;
    end;

  end;

  writeln(u[b[0]]);
end.

Ошибка 201 была из-за того, что элементы массивов u и d могу принимать значения от 0 до 50000. Т.е. всего 50001 значение. Изменение начала массивов на 0-ой элемент решило проблему. Также убрана ошибка в ProcessUD, долгий цикл "for ii:= 1 to pn" перенесен в конец главного цикла в виде проверки "if pad[j].u<u[pad[j].c]".
В тестере все примеры решены.

P.S.: С новым годом =)

Сообщение отредактировано: S_lip - 1.01.2008 22:34

Отлично, поздравляю.

Приходи еще

Спасибо, я заметил.
Кстати, к вопросу об эвристиках:
Решения вида a[n]=a[m] находятся (после сортировки) за O(N), вида a[n]=a[m]+a[k] за O(N*log(N)), a[n]+a[m]=a[k]+a[l] и a[n]=a[m]+a[k]+a[l] - за O(N^2*log(N)).
Правда:
1, 2, 4, 8, 16, 32, 64, 15000, 15128, 15256, ... 29848, 29975 содержит 125 чисел и находится только степенной эвристикой аналогичной тем, что приведены выше, O(N^7*log(N)).

В этой связи возникает еще одна интересная задача: подобрать набор тестов для проверки этой задачи, который бы отсекал все возможные частичные решения. Заодно интересно было бы оценить минимально необходимое количество тестов в этом наборе.

Такая задача возникает всегда. Именно поэтому уровень тех, кто предлагает задачи на олимпиаду, должен как минимум не уступать уровню участников, а в идеале - быть на порядок выше. Как, кстати, и бывает на всероссийской олимпиаде школьников, где каждая задача проходит через семь кругов ада, прежде чем попасть на тур.