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


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

Дан набор из N целых по­ло­жи­тель­ных чисел. Для каж­до­го числа вы­чис­ля­ет­ся сумма двух по­след­них цифр в его де­ся­тич­ной за­пи­си (для од­но­знач­ных чисел пред­по­след­няя цифра счи­та­ет­ся рав­ной нулю). Не­об­хо­ди­мо опре­де­лить,

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

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

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

не более чем в k раз.

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

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

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

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

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

 

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

В пер­вой стро­ке вход­ных дан­ных задаётся ко­ли­че­ство чисел N (1 ≤ N ≤ 1000).

В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 10000.

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

5

15

417

123

6

4841

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

6

Суммы двух по­след­них цифр для чисел из дан­но­го на­бо­ра равны 6, 8, 5, 6, 5.

Чаще дру­гих (по два раза) встре­ча­ют­ся 6 и 5, в от­ве­те вы­во­дит­ся бо́льшая из этих сумм.

Решение.

Сумма двух цифр может принимать значения от 0 до 18. Необходимо создать массив из 19 элементов с индексами от 0 до 18 и использовать его для подсчёта количества чисел с соответствующими суммами двух последних цифр. Использование массива не делает программу неэффективной по памяти, так как размер массива не зависит от N. Затем нужно найти значение максимального элемента этого массива и вывести максимальный из индексов элементов, равных этому максимуму.

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

 

var

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

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

    s: integer; {сумма двух последних цифр}

    d: array [0..18] of integer; {подсчёт сумм}

    mx: integer; {максимальное количество сумм}

    imx: integer; {самая частая сумма}

    i: integer;

begin

    for i:=0 to 18 do d[i]:=0;

    readln(N);

    for i:=1 to N do begin

        readln(a);

        s := a mod 10 + a div 10 mod 10;

        d[s] := d[s]+1;

    end;

    mx := 0;

    for i:=0 to 18 do begin

        if d[i] >= mx then begin

            mx := d[i];

            imx := i;

        

    end;

    writeln(imx)

end.

 

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

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

 

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

var

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

    val: integer; {самая частая сумма}

    a: array [1..1000] of integer;

    max_lenght: integer;

    i, j, k, lenght: integer;

begin

    readln(N);

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

    for i:=1 to N do a[i] := a[i] mod 10 + a[i] div 10 mod 10;

    for i:=1 to N-1 do

        for j:=1 to N-i do

            if a[j] < a[j+1] then begin

                k := a[j];

                a[j] := a[j+1];

                a[j+1] := k;

            end;

    max_lenght := 0;

    lenght := 0;

    val := a[1];

    for i := 1 to N do

        if a[i]=a[i+1] then

            lenght := lenght + 1

        else if lenght>max_lenght then begin

            max_lenght := lenght;

            val := a[i];

            lenght := 0;

        end;

    writeln(val);

    end.