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

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

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

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

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

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

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

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

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

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

m = 80
mn = [0] * m
mx = [0] * m
N = int(input())
for i in range(N):
    x = int(input())
    p = x % m
    if mn[p] == 0 or x < mn[p]:
        mn[p] = x
    if x > mx[p]:
        mx[p] = x
p = 0
for i in range(m):
    if mx[i]-mn[i] > mx[p]-mn[p]:
        p = i
if mx[p] == mn[p]:
    print(0,0)
else:
    print(mn[p], mx[p])

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

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

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

const m=80;
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 (abs(a[i]-a[j]) > abs(x1-x2)) then begin
                x1 := a[i]; x2 := a[j]
            end
        end
    end;
    writeln(x1, ' ', x2)
end.