Алгоритм. Отсортируем массив за O(nlogn). Запустим цикл по всем k, в теле цикла будем искать индексы i <= j, такие, что A[i] + A[j] = -A[k]. Понятно, что этот поиск надо делать за O(n), чтобы общее время работы было квадратичным.
Искать будем с двух указателей. Рассмотрим кусок массива, в котором ищем ответ A[l..r] (первоначально l = 1, r = n). Посмотрим на A[l] + A[r]. Если эта сумма больше, чем нужно, уменьшим на 1 число r, если меньше - увеличим на 1 число l, если равно -A[k] - победа, выводим ответ (l, r, k). Будем повторять это в цикле, пока l не станет больше r.
Если после выполнения цикла по k искомая тройка так и не нашлась, пишем "нет".
Корректность. Пусть в какой-то момент A[l] + A[r] < -A[k]. Тогда, чтобы иметь возможность получить A[i] + A[j] = -A[k], надо сумму увеличить. A[l] оказалось настолько мало, что даже если прибавить к нему самое большое возможное число (а это как раз A[r] - массив-то отсортирован!), то всё равно получается слишком мало. Значит, A[l] в ответе не будет, и можно безбоязненно выкинуть его из рассмотрения. Аналогично будет и в случае, когда A[l] + A[r] > -A[k]. Осталось показать, что если такая тройка индексов существует, то наш алгоритм не выдаст неверный ответ "нет". Но это очевидно: если ответ (I, J, K), то уж при k = K алгоритм что-нибудь да найдёт.
Время работы. Внутренний цикл выдает ответ не более чем за линейное время: всякий раз размер массива уменьшается на 1, всего элементов в массиве n, а на каждом шаге тратится константное время; пусть время выполнения внутреннего цикла T'(n) < an. Тогда все n проходов внешнего цикла затратят время T1(n) <= n T'(n) < an^2. Сортировку можно сделать за время T2(n) < b nlogn < bn^2 Общее время работы T(n) = T1(n) + T2(n) < an^2 + bn^2 = cn^2
должно по идее получиться "нет худо без добра.", но у меня получилось
"нет худо бrз одра." может ты в условии что-то напутала? вот программа которая переводит
function Pow(a, x:integer):integer;
var
rez, i:integer;
begin
rez := 1;
for i := 1 to x do
rez := rez * a;
Pow := rez;
end;
function BinToDec(a:string):integer;
var
i ,r:integer;
begin
r := 0;
for i := length(a) downto 1 do
r := r + StrToInt(a[i]) * Pow(2, length(a) - i);
BinToDec := r;
end;
var
s:array[1..100] of string;
i:integer;
begin
s[1] := '11001101';
s[2] := '11100101';
s[3] := '11110010';
s[4] := '00100000';
s[5] := '11110101';
s[6] := '11110011';
s[7] := '11100100';
s[8] := '11100000';
s[9] := '00100000';
s[10] := '11100001';
s[11] := '1110010';
s[12] := '11100111';
s[13] := '00100000';
s[14] := '11101110';
s[15] := '11100001';
s[16] := '11110000';
s[17] := '11100000';
s[18] := '00101110';
for i := 1 to 18 do
write(chr(BinToDec(s[i])));
end.