Задания
Версия для печати и копирования в MS Word
Тип Д27 C4 № 13503
i

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

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

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

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

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

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

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

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

 

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

3

15

25

32

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

5 2

 

В де­ся­тич­ной за­пи­си чисел за­дан­но­го на­бо­ра чаще всего  — по 2 раза  — встре­ча­ют­ся цифры 2 и 5, в от­ве­те они вы­ве­де­ны в по­ряд­ке убы­ва­ния.

Спрятать решение

Ре­ше­ние.

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

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

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

 

var

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

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

digit: integer; {цифра числа}

d: array [0..9] of integer; {подсчёт цифр}

mx: integer; {мак­си­маль­ное ко­ли­че­ство цифр}

i: integer;

begin

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

readln(N);

for i:=1 to N do begin

readln(a);

while a>0 do begin

digit := a mod 10;

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

a := a div 10;

end;

end;

mx := 0;

for i:=0 to 9 do begin

if d[i] > mx then mx := d[i];

end;

for i:=9 downto 0 do begin

if d[i]=mx then write(i, ' ');

end;

end.

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

 

var

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

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

digit: integer; {ко­ли­че­ство всех цифер ис­ход­ных чисел}

d: array [1..4000] of integer; {подсчёт цифр}

max_lenght: integer;

i, j, k, lenght: integer;

begin

readln(N);

digit := 1;

for i := 1 to 4000 do d[i]:=0;

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

for i := 1 to N do

while a[i]<>0 do begin

d[digit] := a[i] mod 10;

digit := digit+1;

a[i] := a[i] div 10;

end;

for i :=1 to digit-1 do

for j:= 1 to digit-1-i do

if d[j] k := d[j];

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

d[j+1] := k;

end;

max_lenght := 0;

lenght := 1;

for i := 1 to digit-1 do

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

lenght := lenght + 1

else begin

if lenght>max_lenght then begin

max_lenght := lenght;

end;

lenght := 1;

end;

lenght := 1;

for i := 1 to digit-1 do

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

lenght := lenght + 1

else begin

if lenght=max_lenght then write(d[i], ' ');

lenght := 1;

end;

end.

 

При­во­дим эф­фек­тив­ное ре­ше­ние Игоря Ку­да­ше­ва на Python 3.

n = int(input())

a = [0] * 10

for i in range(n):

    x = int(input())

    while x > 0:

        a[x % 10] += 1

        x //= 10

for i in range(9, -1, -1):

    if a[i] == max(a): print(i, end = ' ')

Спрятать критерии
Критерии проверки:

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

До­пус­ка­ет­ся на­ли­чие в тек­сте про­грам­мы до трёх син­так­си­че­ских оши­бок од­но­го из сле­ду­ю­щих видов:

1) про­пу­щен или не­вер­но ука­зан знак пунк­ту­а­ции;

2) не­вер­но на­пи­са­но или про­пу­ще­но за­ре­зер­ви­ро­ван­ное слово языка про­грам­ми­ро­ва­ния;

3) не опи­са­на или не­вер­но опи­са­на пе­ре­мен­ная;

4) при­ме­ня­ет­ся опе­ра­ция, не­до­пу­сти­мая для со­от­вет­ству­ю­ще­го типа дан­ных.

Если одна и та же ошиб­ка встре­ча­ет­ся не­сколь­ко раз, это счи­та­ет­ся за одну ошиб­ку

4
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 4 балла Про­грам­ма в целом ра­бо­та­ет пра­виль­но для любых вход­ных дан­ных про­из­воль­но­го раз­ме­ра. Время ра­бо­ты про­пор­ци­о­наль­но ко­ли­че­ству введённых чисел, пра­виль­но ука­за­но, какие ве­ли­чи­ны долж­ны вы­чис­лять­ся по ходу чте­ния эле­мен­тов по­сле­до­ва­тель­но­сти чисел. Ис­поль­зу­е­мая па­мять, воз­мож­но, за­ви­сит от ко­ли­че­ства про­чи­тан­ных чисел (на­при­мер, вход­ные дан­ные за­по­ми­на­ют­ся в мас­си­ве, кон­тей­не­ре STL в C++ или дру­гой ана­ло­гич­ной струк­ту­ре дан­ных).

Ко­ли­че­ство син­так­си­че­ских оши­бок (опи­сок), ука­зан­ных в кри­те­ри­ях на 4 балла, – не более пяти.

До­пус­ка­ет­ся на­ли­чие не более одной ошиб­ки сле­ду­ю­щих видов.

1) Ошиб­ка при ини­ци­а­ли­за­ции или от­сут­ствие ини­ци­а­ли­за­ции счётчи­ков.

2) Ис­поль­зо­ва­ние де­ле­ния вме­сто на­хож­де­ния остат­ка (div вме­сто mod в Пас­ка­ле) или на­о­бо­рот.

3) Ошиб­ка при по­стро­е­нии цикла раз­би­е­ния на цифры, из-за ко­то­рой одна цифра не учи­ты­ва­ет­ся или учи­ты­ва­ет­ся лиш­ний ноль.

4) От­сут­ствие ини­ци­а­ли­за­ции или не­вер­ная ини­ци­а­ли­за­ция мак­си­му­ма.

5) До­пу­щен выход за гра­ни­цу мас­си­ва.

6) Вме­сто мак­си­му­ма ищет­ся ми­ни­мум.

7) При на­ли­чии не­сколь­ких от­ве­тов вы­во­дят­ся не все от­ве­ты или вывод про­из­во­дит­ся в не­вер­ном по­ряд­ке (не по убы­ва­нию).

8) Вме­сто цифры (ин­дек­са мас­си­ва счётчи­ков) вы­во­дит­ся ко­ли­че­ство (зна­че­ние эле­мен­та)

3
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 3 или 4 балла. Про­грам­ма ра­бо­та­ет в целом верно, эф­фек­тив­но или нет, но в ре­а­ли­за­ции ал­го­рит­ма есть до трёх со­дер­жа­тель­ных оши­бок, опи­сан­ных в кри­те­ри­ях на 3 балла. Ко­ли­че­ство син­так­си­че­ских оши­бок, ука­зан­ных в кри­те­ри­ях на 4 балла, не долж­но быть более де­вя­ти2
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 2, 3 или 4 балла. Про­грам­ма ра­бо­та­ет пра­виль­но в от­дель­ных част­ных слу­ча­ях. До­пус­ка­ет­ся любое ко­ли­че­ство син­так­си­че­ских оши­бок1
Не вы­пол­не­ны кри­те­рии, поз­во­ля­ю­щие по­ста­вить 1, 2, 3 или 4 балла0
Ито­го­вый мак­си­маль­ный балл4