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

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

 

6

А+B

Кре­сти­ки-Но­ли­ки

А+В

Про­стой де­ли­тель

А+В

Про­стой де­ли­тель

 

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

 

Кре­сти­ки-Но­ли­ки 1

Про­стой де­ли­тель 2

А+В 3

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

Ре­ше­ние.

Про­грам­ма чи­та­ет все вход­ные дан­ные один раз, не за­по­ми­ная их в мас­си­ве, раз­мер ко­то­ро­го равен N, а со­став­ляя толь­ко спи­сок встре­тив­ших­ся задач и ко­ли­че­ства за­про­сов по каж­дой из них. Во время чте­ния дан­ных об оче­ред­ной за­да­че про­смат­ри­ва­ет­ся спи­сок ранее со­хранённых задач; если она уже есть в спис­ке, то ко­ли­че­ство за­про­сов по ней уве­ли­чи­ва­ет­ся на 1, иначе за­да­ча до­бав­ля­ет­ся в мас­сив упо­мя­ну­тых в за­про­сах задач (при кор­рект­ных дан­ных раз­мер мас­си­ва не может быть боль­ше 12). После окон­ча­ния ввода про­из­во­дит­ся сор­ти­ров­ка мас­си­вов задач и ко­ли­че­ства за­про­сов, от­дан­ных за них, в по­ряд­ке воз­рас­та­ния ко­ли­че­ства за­про­сов; затем вы­во­дит­ся спи­сок из трёх пер­вых задач с ука­за­ни­ем ча­сто­ты встре­ча­е­мо­сти (или весь спи­сок, если его длина мень­ше трёх). Вме­сто сор­ти­ров­ки можно при­ме­нить и ал­го­ритм по­ис­ка трёх ми­ни­маль­ных эле­мен­тов в мас­си­ве или три пер­вых ите­ра­ции сор­ти­ров­ки. Затем вы­во­дят­ся три пер­вые (или най­ден­ные на­и­ме­нее по­пу­ляр­ные) за­да­чи. Баллы на­чис­ля­ют­ся толь­ко за про­грам­му, ко­то­рая ре­ша­ет за­да­чу хотя бы для од­но­го част­но­го слу­чая. Ниже при­ве­де­ны при­ме­ры ре­ше­ния за­да­ния на язы­ках Пас­каль и Бей­сик. До­пус­ка­ют­ся ре­ше­ния, за­пи­сан­ные на дру­гих язы­ках про­грам­ми­ро­ва­ния. При оце­ни­ва­нии ре­ше­ний на дру­гих язы­ках про­грам­ми­ро­ва­ния не­об­хо­ди­мо учи­ты­вать осо­бен­но­сти этих язы­ков про­грам­ми­ро­ва­ния. Так, на языке C++ при счи­ты­ва­нии стро­ко­вой пе­ре­мен­ной будет счи­та­но не всё на­зва­ние за­да­чи, а толь­ко его пер­вое слово, по­это­му сле­ду­ет ис­поль­зо­вать функ­цию getline(cin,s); ана­ло­гич­ная про­бле­ма воз­ни­ка­ет и в языке Си

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

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

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

s: string;

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

Begin

Num:=0; {Число раз­лич­ных задач в спис­ке за­про­сов}

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

for i:=1 to N do

begin

ReadLn(S); {счи­та­ли оче­ред­ную за­да­чу}

{Осу­ществ­ля­ем её поиск в спис­ке уже встре­тив­ших­ся}

j:=1;

while (j<=Num) and (s<>Names[j]) do j:=j+1;

{Если она най­де­на}

if j<=Num then {Уве­ли­чи­ва­ем счет­чик числа за­про­сов}

Count[j]:=Count[j]+1

else begin {Иначе до­бав­ля­ем за­да­чу в конец спис­ка}

Names[j]:=s;

Count[j]:=1;

Num:=Num+1

end

end;

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

for i:=Num 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;

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

end;

if Num >= 3 then Num := 3;

for i:=1 to Num do

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

end.

DIM N, Num, i, j, t AS INTEGER

DIM Count(12) AS INTEGER

DIM Names$(12)

Num = 0 'Число раз­лич­ных задач в спис­ке за­про­сов

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

FOR i = 1 TO N

LINE INPUT s$ 'счи­та­ли за­да­чу

'Осу­ществ­ля­ем поиск за­да­чи в спис­ке уже встре­тив­ших­ся

j = 1

WHILE (j <= Num) AND (s$ <> Names$(j))

j = j + 1

WEND

'Если за­да­ча най­де­на

IF j <= Num THEN 'Уве­ли­чи­ва­ем счет­чик числа за­про­сов

Count(j) = Count(j) + 1

ELSE ' Иначе до­бав­ля­ем за­да­чу в конец спис­ка

Names$(j) = s$

Count(j) = 1

Num = Num + 1

END IF

NEXT i

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

'мас­си­ва Count

FOR i = Num 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

s$ = Names$(j): Names$(j) = Names$(j - 1): Names$(j - 1) = s$

END IF

NEXT j

NEXT i

IF Num >= 3 THEN Num = 3

FOR i = 1 TO Num

PRINT Names$(i), Count(i)

NEXT i

END

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

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


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