РЕШУ ЕГЭ — информатика

Задания

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

А+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

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

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

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

Ключ