Pascal. Задача 8-40
На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности ai и aj, такие что i < j и ai > aj (первый элемент пары больше второго; i и j — порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 120. Если среди найденных пар максимальную сумму имеют несколько, то необходимо вывести последнюю их них.
Входные данные: Дан входной файл, в первой строке которого задаётся количество чисел n (2 ≤ n ≤ 100 000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, то необходимо вывести из них последнюю, встреченную в файле . Гарантируется, что хотя бы одна такая пара в последовательности есть.
Пример входных данных:
6
60
140
61
100
300
59
Пример выходных данных для приведённого выше примера входных данных: 140 100
Пояснение. Из шести заданных чисел можно составить три пары, сумма элементов которых делится на m=120: 60+300, 140+100 и 61+59. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.
const
m = 120;
var
N, i, p, cur, left, right : integer;
a : array[1..m] of integer;
s : string;
f : text;
begin
left := 0;
right := 0;
for i := 1 to m do a[i] := 0;
Assign(f,'C:\PABCWork.NET\test-8-40-1.txt');
Reset(f);
Readln(f, N);
for i := 1 to N do begin
Readln(f, cur);
p := cur mod m + 1;
if p = 1 then begin
if (a[1] > cur) and (a[1] + cur >= left + right) then begin
left := a[1];
right := cur;
end;
end
else
if (a[m - p + 2] > cur) and (a[m - p + 2] + cur >= left + right) then begin
left := a[m - p + 2];
right := cur;
end;
if a[p] < cur then a[p] := cur;
end;
Close(f);
Writeln(left, ' ', right);
end.