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. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.

 

Ответ
9979 9941
Решение
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.