СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 27 № 15964

Дан набор из N целых по­ло­жи­тель­ных чисел. Из них нужно вы­брать и вы­ве­сти два числа так, чтобы их сумма была нечётна, а про­из­ве­де­ние де­ли­лось на 5 и при этом было мак­си­маль­но воз­мож­ным. Вы­бран­ные числа можно вы­во­дить в любом по­ряд­ке. Если есть не­сколь­ко под­хо­дя­щих пар, можно вы­брать любую из них. Если под­хо­дя­щих пар нет, нужно вы­ве­сти 0.

На­пи­ши­те эф­фек­тив­ную по вре­ме­ни и по па­мя­ти про­грам­му для ре­ше­ния этой за­да­чи.

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если при уве­ли­че­нии ко­ли­че­ства ис­ход­ных чисел N в k раз время ра­бо­ты про­грам­мы уве­ли­чи­ва­ет­ся не более чем в k раз.

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

Мак­си­маль­ная оцен­ка за пра­виль­ную (не со­дер­жа­щую син­так­си­че­ских оши­бок и да­ю­щую пра­виль­ный ответ при любых до­пу­сти­мых вход­ных дан­ных) про­грам­му, эф­фек­тив­ную по вре­ме­ни и по па­мя­ти, — 4 балла.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную толь­ко по вре­ме­ни или толь­ко по па­мя­ти, — 3 балла.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, не удо­вле­тво­ря­ю­щую тре­бо­ва­ни­ям эф­фек­тив­но­сти, — 2 балла.

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

Перед тек­стом про­грам­мы крат­ко опи­ши­те ал­го­ритм ре­ше­ния. Ука­жи­те ис­поль­зо­ван­ный язык про­грам­ми­ро­ва­ния и его вер­сию.

Опи­са­ние вход­ных и вы­ход­ных дан­ных.

В пер­вой стро­ке вход­ных дан­ных задаётся ко­ли­че­ство чисел N (1 ≤ N ≤ 1000). В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 100.

При­мер вход­ных дан­ных:

5

1

2

4

5

7

При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных:

4 5

Из 5 чисел можно со­ста­вить 10 пар. В дан­ном слу­чае усло­ви­ям удо­вле­тво­ря­ют две пары: (2, 5) и (4, 5). Суммы чисел в этих парах (7 и 11) нечётны, а про­из­ве­де­ния (10 и 20) де­лят­ся на 5. У всех осталь­ных пар как ми­ни­мум одно из этих усло­вий не вы­пол­ня­ет­ся. Из двух воз­мож­ных пар вы­во­дим ту, в ко­то­рой боль­ше про­из­ве­де­ние эле­мен­тов.

Ре­ше­ние.

Разобьём все числа ис­ход­но­го на­бо­ра на 4 груп­пы в за­ви­си­мо­сти от их чётно­сти и де­ли­мо­сти на 5:

m1 нечётные числа, не крат­ные 5;

m2 чётные числа, не крат­ные 5;

m5 нечётные числа, крат­ные 5;

m10 чётные числа, крат­ные 5.

Чтобы сумма двух чисел было нечётной, одно из них долж­но быть чётным, а дру­гое — нечётным. Чтобы про­из­ве­де­ние двух чисел де­ли­лось на 5, хотя бы одно из этих чисел долж­но де­лить­ся на 5. Таким об­ра­зом, нужно вы­брать два числа из групп m1 и m10, или из групп m2 и m5, или из групп m5 и m10. Чтобы по­лу­чить пару с мак­си­маль­ным про­из­ве­де­ни­ем, до­ста­точ­но со­хра­нить мак­си­маль­ный эле­мент из каж­дой груп­пы, срав­нить со­от­вет­ству­ю­щие про­из­ве­де­ния и вы­брать из них наи­боль­шее.

Сами числа при этом можно не хра­нить, до­ста­точ­но при вводе опре­де­лить оста­ток от де­ле­ния оче­ред­но­го числа на 2 и на 5, срав­нить число с те­ку­щим мак­си­му­мом со­от­вет­ству­ю­щей груп­пы и при не­об­хо­ди­мо­сти об­но­вить этот мак­си­мум и уве­ли­чить со­от­вет­ству­ю­щий счётчик. Таким об­ра­зом, не­за­ви­си­мо от ко­ли­че­ства чисел в ис­ход­ном на­бо­ре, после чте­ния ис­ход­ных дан­ных для хра­не­ния не­об­хо­ди­мой ин­фор­ма­ции хва­тит 4 пе­ре­мен­ных, и про­грам­ма по­лу­чит­ся эф­фек­тив­ной по па­мя­ти.

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

 

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

var

    N: integer; {ко­ли­че­ство чисел}

    a: integer; {оче­ред­ное число}

    m1: integer; {нечётные, не крат­ные 5}

    m2: integer; {чётные, не крат­ные 5}

    m5: integer; {нечётные, крат­ные 5}

    m10: integer; {чётные, крат­ные 5}

    x, y: integer; {вы­бран­ная пара}

    i: integer;

begin

    m1 := 0; m2 := 0; m5 := 0; m10 := 0;

    readln(N);

    for i:=1 to N do begin

        readln(a);

        if a mod 2 = 0 then begin

            if a mod 5 = 0 then begin

                if a>m10 then m10 := a

            end

            else begin

                if a>m2 then m2 := a

            end

        end

        else begin

            if a mod 5 = 0 then begin

                if a>m5 then m5 := a

            else begin

                if a>m1 then m1 := a

            end

        end

    end;

    x := m1; y := m10;

    if m2*m5 > x*y then begin

        x := m2; y := m5;

    end

    if m5*m10 > x*y then begin

        x := m5; y := m10;

    end

    if x*y = 0

        then writeln(0)

        else writeln(x, ' ', y);

end.

 

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

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

 

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

 

var

    N: integer; {ко­ли­че­ство чисел}

    a: array [1..1000] of integer; {ис­ход­ные дан­ные}

    x, y: integer; {вы­бран­ная пара}

    i, j: integer;

begin

    readln(N);

    for i := 1 to N do readln(a[i]);

    x := 0; y := 0;

    for i := 1 to N − 1 do begin

        for j := i + 1 to N do begin

            if ((a[i] + a[j]) mod 2 = 1) and ((a[i]*a[j]) mod 5 = 0) and (a[i](a[j] > x*y) then begin

                x := a[i]; y := a[j];

            end

        end

    end;

    if x = 0

        then writeln(0)

        else writeln(x, ' ', y);

end.

 

При­ведём ре­ше­ние Ев­ге­ния Гоп­та­ря, Pascal.

var 

a, mch5, mch, mnch, mnch5, N, i: integer;

begin

readln(N);

for i:=1 to N do begin

readln(a);

if (a mod 2 = 0) and (a mod 5 = 0) and (a > mch5) then mch5:=a;

if (a mod 2 = 0) and (a mod 5 <> 0) and (a > mch) then mch:=a;

if (a mod 2 <> 0) and (a mod 5 = 0) and (a > mnch5) then mnch5:=a;

if (a mod 2 <> 0) and (a mod 5 <> 0) and (a > mnch) then mnch:=a;

end;

if (mch5*mnch>=mch*mnch5) then writeln (mch5, ' ', mnch);

if (mch*mnch5 > mch5*mnch) then writeln (mch, ' ', mnch5);

if (mnch5*mch5 > mch*mnch5) and (mnch5*mch5 > mch5*mnch) then writeln (mch5, ' ', mnch5);

end.