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

В ко­манд­ных олим­пи­а­дах по про­грам­ми­ро­ва­нию для ре­ше­ния пред­ла­га­ет­ся не боль­ше 12 задач. Ко­ман­да может ре­шать пред­ло­жен­ные за­да­чи в любом по­ряд­ке. Под­го­тов­лен­ные ре­ше­ния ко­ман­да по­сы­ла­ет в еди­ную про­ве­ря­ю­щую си­сте­му со­рев­но­ва­ний. Вам пред­ла­га­ет­ся на­пи­сать эф­фек­тив­ную, в том числе по ис­поль­зу­е­мой па­мя­ти, про­грам­му, ко­то­рая будет ста­ти­сти­че­ски об­ра­ба­ты­вать при­шед­шие за­про­сы на про­вер­ку, чтобы опре­де­лить по­пу­ляр­ность той или иной за­да­чи. Сле­ду­ет учи­ты­вать, что ко­ли­че­ство за­про­сов в спис­ке может быть очень ве­ли­ко, так как мно­гие со­рев­но­ва­ния про­хо­дят с ис­поль­зо­ва­ни­ем сети Ин­тер­нет. Перед тек­стом про­грам­мы крат­ко опи­ши­те ис­поль­зу­е­мый Вами ал­го­ритм ре­ше­ния за­да­чи. На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство при­шед­ших за­про­сов N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­сан номер за­да­чи от 1 до 12. При­мер вход­ных дан­ных:

 

6

1

2

1

1

5

2

 

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

 

1 3

2 2

5 1

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

Ре­ше­ние.

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

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

Var n, Num, i, j, t: integer;

Count: array[1..12] of integer;

Names: array[1..12] of integer;

Begin

For i := 1 to 12 do

begin

Count[i] := 0;

Names[i] := i;

end;

ReadLn(N); { Счи­ты­ва­ем ко­ли­че­ство за­про­сов}

for i:=1 to N do

begin

ReadLn(t); {счи­та­ли оче­ред­ной за­прос}

Count[t] := Count[t] + 1;

end;

{Сор­ти­ру­ем мас­си­вы Names и Count в по­ряд­ке убы­ва­ния зна­че­ний мас­си­ва Count}

for i:=12 downto 2 do

for j:=2 to i do if Count[j-1] < Count[j] then

begin

t:=Count[j]; Count[j]:=Count[j-1]; Count[j-1]:=t;

t:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=t;

end;

for i:=1 to 12 do

if Count[i] > 0 then

WriteLn(Names[i], ' ', Count[i]);

end.

DIM N, i, j, t AS INTEGER

DIM Count(12) AS INTEGER

DIM Names(12) AS INTEGER

FOR i = 1 TO 12

Count(i) = 0

Names(i) = i

NEXT i

INPUT N '

Счи­ты­ва­ем ко­ли­че­ство за­про­сов

FOR i = 1 TO N

INPUT t '

счи­та­ли за­да­чу

'Под­счи­ты­ва­ем её

Count(t) = Count(t) + 1

NEXT i

'Сор­ти­ру­ем мас­си­вы Names и Count в по­ряд­ке убы­ва­ния

'зна­че­ний мас­си­ва Count

FOR i = 12 TO 2 STEP -1

FOR j = 2 TO i

IF Count(j - 1) < Count(j) THEN

t = Count(j): Count(j) = Count(j - 1): Count(j - 1) = t

t = Names(j): Names(j) = Names(j - 1): Names(j - 1) = t

END IF

NEXT j

NEXT i

FOR i = 1 TO 12

IF Count(i) > 0 THEN PRINT Names(i), Count(i)

NEXT i

END

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

Кри­те­рии оце­ни­ва­ния вы­пол­не­ния за­да­нияБаллы
Про­грам­ма ра­бо­та­ет для любых вход­ных дан­ных про­из­воль­но­го раз­ме­ра и на­хо­дит ответ, не со­хра­няя вход­ные дан­ные в мас­си­ве, раз­мер ко­то­ро­го со­от­вет­ству­ет числу N (ко­ли­че­ству за­про­сов), а под­счи­ты­вая в мас­си­ве раз­ме­ром 12, сколь­ко раз встре­ти­лась та или иная за­да­ча. До­пус­ка­ет­ся на­ли­чие в тек­сте про­грам­мы трёх син­так­си­че­ских оши­бок: про­пу­щен или не­вер­но ука­зан знак пунк­ту­а­ции; не­вер­но на­пи­са­но или про­пу­ще­но за­ре­зер­ви­ро­ван­ное слово языка про­грам­ми­ро­ва­ния; не опи­са­на или не­вер­но опи­са­на пе­ре­мен­ная; при­ме­ня­ет­ся опе­ра­ция, не­до­пу­сти­мая для со­от­вет­ству­ю­ще­го типа дан­ных (если одна и та же ошиб­ка встре­ча­ет­ся не­сколь­ко раз, то это счи­та­ет­ся за одну ошиб­ку) 4
Про­грам­ма ра­бо­та­ет верно, но вход­ные дан­ные со­хра­ня­ют­ся в мас­си­ве, раз­мер ко­то­ро­го со­от­вет­ству­ет числу N. Этот мас­сив, воз­мож­но, потом сор­ти­ру­ет­ся. Или для уве­ли­че­ния числа встре­ча­е­мо­сти оче­ред­ной за­да­чи ис­поль­зу­ет­ся цикл от 1 до 12, или опе­ра­тор case, или 12 опе­ра­то­ров if. До­пус­ка­ет­ся на­ли­чие до пяти син­так­си­че­ских оши­бок, опи­сан­ных выше. Воз­мож­но, в прин­ци­пи­аль­но верно ор­га­ни­зо­ван­ном вводе дан­ных есть одна ошиб­ка. 3 балла также вы­став­ля­ет­ся, если в эф­фек­тив­ной про­грам­ме, удо­вле­тво­ря­ю­щей кри­те­ри­ям вы­став­ле­ния 4 бал­лов, есть одна ошиб­ка, в ре­зуль­та­те ко­то­рой про­грам­ма ра­бо­та­ет не­вер­но на не­ко­то­рых на­бо­рах не­ти­пич­ных вход­ных дан­ных (на­при­мер, все за­про­сы от­но­сят­ся к одной и той же за­да­че). Также 3 балла вы­став­ля­ет­ся, если про­грам­ма вы­во­дит на экран все за­да­чи с вер­ным чис­лом за­про­сов, но среди них есть и те, ко­то­рые не встре­ча­ют­ся в спис­ке ис­ход­ных дан­ных (вы­во­дят­ся за­да­чи, на ко­то­рые не было за­про­сов, с ука­за­ни­ем ко­ли­че­ства за­про­сов, рав­но­го 0)3
Про­грам­ма ра­бо­та­ет в целом верно, эф­фек­тив­но или нет, но в ре­а­ли­за­ции ал­го­рит­ма со­дер­жит­ся до двух оши­бок (не­вер­ная ини­ци­а­ли­за­ция счет­чи­ков, хотя в пред­ло­жен­ных выше ре­ше­ни­ях об­ну­лять их не тре­бу­ет­ся; воз­мож­но, про­грам­ма ра­бо­та­ет не­вер­но, если в спис­ке упо­мя­ну­то мень­ше 12 задач, выход за гра­ни­цу мас­си­ва, до­пу­ще­на ошиб­ка в прин­ци­пи­аль­но верно ор­га­ни­зо­ван­ной сор­ти­ров­ке, ис­поль­зу­ет­ся знак “<” вме­сто “<=”, “or” вме­сто “and” и т.п.). Воз­мож­но, не­кор­рект­но ор­га­ни­зо­ва­но счи­ты­ва­ние вход­ных дан­ных. До­пус­ка­ет­ся на­ли­чие до семи син­так­си­че­ских оши­бок, опи­сан­ных выше2
Про­грам­ма, воз­мож­но, ра­бо­та­ет не­вер­но при не­ко­то­рых вход­ных дан­ных, но по при­ведённому тек­сту ре­ше­ния ясно, что эк­за­ме­ну­е­мый по­ни­ма­ет, из каких эта­пов долж­но со­сто­ять ре­ше­ние за­да­чи. При ис­поль­зо­ва­нии сор­ти­ров­ки она может быть ре­а­ли­зо­ва­на прин­ци­пи­аль­но не­вер­но (на­при­мер, вме­сто двух цик­лов ис­поль­зу­ет­ся один). Всего до­пус­ка­ет­ся до четырёх раз­лич­ных оши­бок в ре­а­ли­за­ции ал­го­рит­ма, в том числе опи­сан­ных в кри­те­ри­ях при­сво­е­ния 2 бал­лов. До­пус­ка­ет­ся на­ли­чие лю­бо­го ко­ли­че­ства син­так­си­че­ских оши­бок, опи­сан­ных выше1
За­да­ние не вы­пол­не­но или вы­пол­не­но не­вер­но0
Мак­си­маль­ный балл4
Источник: ЕГЭ по ин­фор­ма­ти­ке 08.07.2013. Вто­рая волна. Ва­ри­ант 601
Спрятать решение · КритерииСпрятать критерии · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026