Сумма двух чисел крат­на m, остат­ки от де­ле­ния этих чисел на m равны. При этом для по­лу­че­ния мак­си­маль­ной суммы нужно взять два наи­боль­ших числа с оди­на­ко­вым остат­ком.

Будем хра­нить в одном мас­си­ве из m эле­мен­тов мак­си­маль­ные числа, име­ю­щие со­от­вет­ству­ю­щий оста­ток от де­ле­ния на m, а в дру­гом  — вто­рые по ве­ли­чи­не, и из всех таких пар вы­бе­рем пару с наи­боль­шей сум­мой

При этом нужно убе­дить­ся, что вто­рой мак­си­мум су­ще­ству­ет,  — иначе в по­сле­до­ва­тель­но­сти нет двух чисел с таким остат­ком.

Ниже при­ве­де­на про­грам­ма на ал­го­рит­ми­че­ском языке, ре­а­ли­зу­ю­щая этот ал­го­ритм

При­мер 1. Про­грам­ма на языке Пас­каль. Про­грам­ма эф­фек­тив­на по вре­ме­ни и па­мя­ти.

const m = 60;
var 
    m1: array[0..m-1] of integer;
    m2: array[0..m-1] of integer;
    i, N: integer;
    x: integer; | оче­ред­ное число из по­сле­до­ва­тель­но­сти
    p: integer; | оста­ток
    pm: integer; | оста­ток, да­ю­щий луч­шую сумму
    sm: integer; | луч­шая сумма
begin
    for i := 0 to m-1 do begin
        mn[i] := 0; 
        mx[i] := 0;
    end;
    pm := 0;
    sm := 0;
    readln(N);
    for i := 0 to N-1 do begin
        readln(x); 
        p:= x mod m;
        if (x > m1[p]) then begin 
            m2[p] := m1[p];
            m1[p] := x;
        end
        else if (x > m2[p]) then
            m2[p] := x;
        if (m1[p]+m2[p] > sm) and (m2[p] > 0) then begin
            pm := p;
            sm := m1[p] + m2[p];
        end;
    end;
    if sm = 0 then writeln('0 0')
    else writeln(m1[pm], '  ', m2[pm]);
end.

В при­ведённом ре­ше­нии луч­шая пара на­хо­дит­ся «на лету»: после об­ра­бот­ки каж­до­го числа из по­сле­до­ва­тель­но­сти про­ве­ря­ет­ся, не уве­ли­чи­лась ли воз­мож­ная сумма.

Эту про­вер­ку можно про­ве­сти после за­вер­ше­ния ввода, вы­чис­лив суммы для всех остат­ков и срав­нив их. Такая про­грам­ма тоже эф­фек­тив­на по вре­ме­ни и по па­мя­ти, а при боль­ших N она ра­бо­та­ет даже быст­рее преды­ду­щей, т. к. вы­пол­ня­ет мень­ше вы­чис­ле­ний и срав­не­ний.

Ниже при­ве­де­на ре­а­ли­зу­ю­щая этот ал­го­ритм про­грам­ма на языке Python

При­мер 2. Пра­виль­ная, но не­эф­фек­тив­ная про­грам­ма на языке Python.

m = 60
m1 = [0] * m
m2 = [0] * m
N = int(input())
for i in range(N):
    x = int(input())
    p = x % m
    if x > m1[p]:
        m2[p] = m1[p]
        m1[p] = x
    elif x > m2[p]:
        m2[p] = x
p = 0; s = 0
for i in range(m):
    if m2[i] > 0 and m1[i]+m2[i]> s:
        p = i
        s = m1[i]+m2[i]
if s == 0:
    print(0,0)
else:
    print(m1[p], m2[p])

Воз­мож­но также «ло­бо­вое» ре­ше­ние: за­пи­шем все ис­ход­ные числа в мас­сив, пе­ре­берём все воз­мож­ные пары и вы­бе­рем под­хо­дя­щую. Такое ре­ше­ние не яв­ля­ет­ся эф­фек­тив­ным ни по па­мя­ти (тре­бу­е­мая па­мять за­ви­сит от раз­ме­ра ис­ход­ных дан­ных), ни по вре­ме­ни (ко­ли­че­ство воз­мож­ных пар, а зна­чит, ко­ли­че­ство дей­ствий и время счёта с ро­стом ко­ли­че­ства ис­ход­ных эле­мен­тов растёт квад­ра­тич­но). По­доб­ная про­грам­ма оце­ни­ва­ет­ся не выше 2 бал­лов.

Ниже при­ве­де­на ре­а­ли­зу­ю­щая опи­сан­ный выше ал­го­ритм про­грам­ма на языке Пас­каль (ис­поль­зо­ва­на вер­сия PascalABC)

При­мер 3. Пра­виль­ная, но не­эф­фек­тив­ная про­грам­ма на языке Пас­каль.

const m=60;
var
    N: integer; {ко­ли­че­ство чисел}
    a: array [1..10000] of integer; {ис­ход­ные дан­ные}
    x1, x2: integer; {ответ – пара чисел}
    i,j: integer;
begin
    readln(N);
    for i:=1 to N do readln(a[i]);
    x1:=0; x2:=0;
    for i := 1 to N do begin
        for j := i+1 to N do begin
            if ((a[i] - a[j]) mod m = 0) and (a[i]+a[j]) > x1+x2) then begin
                x1:=a[i]; x2:=a[j]
            end
        end
    end;
    writeln(x1, ' ', x2)
end.