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

Каж­дое введённое число будем рас­смат­ри­вать как пра­вый эле­мент воз­мож­ной пары, на­хо­дить со­от­вет­ству­ю­щий ему пар­ный оста­ток, вы­чис­лять про­из­ве­де­ние пары и при не­об­хо­ди­мо­сти об­нов­лять мак­си­мум для про­из­ве­де­ния и для чисел с дан­ным остат­ком

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

const m = 60;
var 
    a: array[0..m-1] of integer;
    i, N: integer;
    x: integer; | оче­ред­ное число из по­сле­до­ва­тель­но­сти
    p, pp: integer; | оста­ток и пар­ный ему оста­ток
    x1, x2: integer; | ответ  — пара чисел
begin
    for i := 0 to m-1 do begin
        a[i] := 0;
    end;
    x1:= 0;
    x2:= 0;
    readln(N);
    for i := 0 to N-1 do begin
        readln(x); 
        p:= x mod m;
        pp:= (m - p) mod m;
        if (x*a[pp] > x1*x2) then begin 
            x1 := a[pp];
            x2 := x;
        end;
        if (x > a[p]) then
            a[p] := x;
    end;
    writeln(x1, '  ', x2);
end.

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

По­ря­док про­вер­ки усло­вий (сна­ча­ла об­нов­ле­ние про­из­ве­де­ния, затем  — эле­мен­та мас­си­ва) важен. Если сна­ча­ла об­но­вить мас­сив, то при p  =  0 и p  =  m/2 вме­сто про­из­ве­де­ния двух раз­ных эле­мен­тов может быть по­лу­чен квад­рат од­но­го эле­мен­та по­сле­до­ва­тель­но­сти.

В про­грам­ме нет спе­ци­аль­ной про­вер­ки на­ли­чия в по­сле­до­ва­тель­но­сти под­хо­дя­щих пар, но если их нет, пе­ре­мен­ные x1 и x2 со­хра­нят за­дан­ные в на­ча­ле про­грам­мы ну­ле­вые зна­че­ния и будет вы­ве­ден вер­ный ответ.

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

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

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

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]; x[2]:=a[j]
            end
        end
    end;
    writeln(x1, ' ', x2)
end.