Нахождение двух минимальных сумм чисел Опции

[S_lip]

Здравствуйте!
Вот такая задачка:

Дана упорядоченная последовательность N чисел. (2<=N<=200). Каждое число больше 0, но меньше 30000. Нужно из этого ряда найти два набора чисел, величины которых должны быть равны и минимальны. Гарантируется, что эта величина будет меньше 100000. Эту величину нужно выписать.

Примеры:
Дано: 1 2 3 4 5. Группы чисел: 1 2 и 3. Ответ: 3.
Дано: 1 2 5 5 8 10 102. Группы чисел: 5 и 5. Ответ: 5.
Дано: 2 3 4 5. Группы чисел: 2 3 и 5. Ответ: 5.
Дано: 1 3 5 7 13 21. Группы чисел: 1 7 и 3 5. Ответ: 8.
Дано: 1 2 5 8 14. Группы чисел: 1 2 5 и 8. Ответ: 8.


Вот я придумал вот такое решение:
http://img401.imageshack.us/img401/500/20308125la9.png

const
  MaxCount=200;
  MaxSum=100000;
type
  pair=record
    l,r:longint;
  end;
var
  a:array [1..MaxCount] of integer;
  b:array [0..50000] of pair; //чтоб хватило
  f:text;
  n,i,j,k,d:integer;
begin
  assign(f,'file.in');
  reset(f);
  readln(f,n);
  for i:= 1 to n do readln(f,a[i]);
  close(f);

  d:=0;
  repeat
    inc(d);
    b[0].l:=a[d];
    b[0].r:=0;
    i:=1;
    k:=d;

    repeat
      inc(k);
      for j:= 0 to (i-1) do begin
        b[j+i].l:=b[j].l;
        b[j+i].r:=b[j].r+a[k];
        inc(b[j].l , a[k]);
      end;
      j:=1;
      inc(i,i);
      while (j<=i) and (b[j-1].l<>b[j-1].r) do inc(j);
    until(j<=i) or (b[0].l>MaxSum)

  until j<=i;
  
  writeln(b[j-1].l);
end.

Программа перебирает все возможне пары сначало с участием первого числа. Если сумма этих пар больше 100000, а равные величины так и не найдены, то перебирает все возможные пары с участием второго числа и т.д.

Это решение кушает очень много памяти и при большом N вылетает. Возможно, есть более элегантное и правильное решение? =)

[S_lip]

andriano, мне не нужен ни один из предложенных вариантов. Мне нужно, что программа всегда давала правильный ответ за ограниченное время работы (не дольше 1 секунды). Именно такой программой и является мой последний выложенный код.

Ко всем: если кто может, помогите найти такие входные файлы, чтобы эта программа давала неправильный ответ, т.к. все тесты, которые я пробовал, она проходила на "ура".

Вот небольшое разъяснение работы моего кода, которое поможет вам в ней разобраться и, возможно, найти такую цепь, при которой прога давала бы неправильный ответ.
1) Массивы "u" и "d" содержат все возможные минимальные наборы чисел от 1 до i элемента в цепи. Причем для удобства u[num]<=d[num].
2) Под минимальными имеется ввиду следующее: например сдери массивов уже имеются такие пары: u[num1]=1 d[num1]=8 и u[num2]=0 d[num2]=7. Первая пара нам не нужна, т.к. если следующая i будет 7, то в качестве ответа подойдет и 7 (0+7=7) и 8 (1+7=8). Поэтому после всех добавления в массивы u и d всех новых пар с участием i, идет отсеивание ненужных пар.
3) Чтобы каждый раз не сортировать массивы u и d, используется массив b, каждый элемент которого указывает на пару в массива u и d с соответствующей разностью. Например, в случае с u[num1]=1 d[num1]=8 и u[num2]=0 d[num2]=7, b[8-1]=num1, а b[7-0]=num2. Понятно, что b[7] может хранить только одно значение. В нашем случае - b[7]=num2, т.к. u[num2]=0 d[num2]=7 - минимальны.

Разберем пример цепи из 4-ех чисел: 1 3 5 7.
1) сначало копируем первый элемент(1):
u d
0 1
b= ( 0,1,0,0,0,0,0,0...). Именно так потому, что d[1]-u[1]=1, а массив b начинается с 0-ого элемента.
2) второй элемент(3):
u d
0 1 - этот был.
0 3 - этот добавляем с учетом, что ответ будет включать в себя 2-ой эл-т, но не будет то, что было.
0 4 - один набор включает то, что было в d + 3, а второй - то, что было в u.
1 3 - наобарот. один набор включает то, что было в u + 3, а второй - то, что было в d. Переверачиваем,т.к. u[4]>d[4].
b= ( 0,1,4,2,3,0,0,0...).
3) третий элемен(5):
u d
0 1 - был.
0 3 - был.
0 4 - был.
1 3 - был.
0 5 - этот добавляем с учетом, что ответ будет включать в себя 3-ий эл-т, но не будет то, что было.
0 6 - один набор включает то, что было в d[1] + 5, а второй - то, что было в u[1].
1 5 - наобарот. один набор включает то, что было в u[1] + 5, а второй - то, что было в d[1]. Переверачиваем,т.к. u[8]>d[8].
0 8 - u[2]/d[2]+5.
3 5 - u[2]+5/d[2]. Переворачиваем.
0 9 - u[3]/d[3]+5.
4 5 - u[3]+5/d[3]. Переворачиваем.
1 8 - u[4]/d[4]+5.
3 6 - u[4]+5/d[4]. Переворачиваем.
Теперь отсеиваем ненужные: 1/5 (т.к. есть 0/4), 3/5 (есть 1/3), 4/5 (0/1), 3/6 (0/3).
Получаем:
0 1
0 3
0 4
1 3
0 5
0 6
1 8
0 8
0 9
b= (0,1,4,2,3,5,6,7,8,9)
4) четвертый элемен(7):
0 1
0 3
0 4
1 3
0 5
0 6
1 8
0 8
0 9
0 7
0 8
1 7
0 10
3 7
0 11
4 7
1 10
3 8
0 12
5 7
0 13
6 7
0 15
7 8
0 16
7 9
1 15
8 8
Отсеиваем ненужные. Получаем:
0 1
0 3
0 4
1 3
0 5
0 6
1 8
0 8
0 9
0 7
0 10
0 11
0 12
0 13
0 15
0 16
1 15
8 8
b= (18,1,4,2,3,5,6,9,7...)
Ура! b[0]>0. ответ: u[b[0]]. т.е. - 8