Алгоритм. Отсортируем массив за 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
type
base = record
id: integer;
ball: integer;
end;
var
t: text;
a: array of array of integer;
n: integer;
st, tmp: string;
err: integer := 1;
database: base;
begin
readln(n);
setlength(a, n);
for i: integer := low(a) to high(a) do
setlength(a[i], 2);
for i: integer := low(a) to high(a) do
begin
readln(st);
tmp := st;
delete(tmp, pos(' ', tmp, err), tmp.Length - pos(' ', tmp, err) + 1);
database.id := strtoint(tmp);
tmp := st;
delete(tmp, 1, pos(' ', tmp, err));
database.ball := strtoint(tmp);
a[i, 0] := database.id;
a[i, 1] := database.ball;
end;
var j: integer := 0;
assign(t, 'output.txt');
rewrite(t);
while (j <= high(a)) do
begin
if (j + 1 < high(a)) and (a[j, 1] = a[j + 1, 1]) then
if (a[j, 0] < a[j + 1, 0]) then begin
write(t, inttostr(a[j, 0])); write(t, ' '); write(t, inttostr(a[j, 1])); writeln(t,'');
write(t, inttostr(a[j + 1, 0])); write(t, ' '); write(t, inttostr(a[j + 1, 1])); writeln(t,'');
end else begin
write(t, inttostr(a[j + 1, 0])); write(t, ' '); write(t, inttostr(a[j + 1, 1])); writeln(t,'');
write(t, inttostr(a[j, 0])); write(t, ' '); write(t, inttostr(a[j, 1])); writeln(t,'');
end;
if (j+1=n) then
write(t, inttostr(a[j, 0])); write(t, ' '); write(t, inttostr(a[j, 1])); writeln(t,'');
inc(j, 2);
end;
close(t);
end.