Вот такая задачка:
Дана упорядоченная последовательность 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 вылетает. Возможно, есть более элегантное и правильное решение? =)