В командных олимпиадах по программированию для решения предлагается
не больше 11 задач. Команда может решать предложенные задачи в любом
порядке. Подготовленные решения команда посылает в единую
проверяющую систему соревнований.
Вам предлагается написать
эффективную, в том числе по используемой памяти, программу, которая
будет статистически обрабатывать пришедшие запросы, чтобы определить
наиболее популярные задачи.
Следует учитывать, что количество запросов в
списке может быть очень велико, так как многие соревнования проходят с
использованием Интернет.
Перед текстом программы кратко опишите используемый вами алгоритм
решения задачи.
На вход программе в первой строке подаётся количество пришедших
запросов В каждой из последующих строк записано название задачи
в виде текстовой строки. Длина строки не превосходит 100 символов,
название может содержать буквы, цифры, пробелы и знаки препинания.
Пример входных данных:
6 А+B
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель
Программа должна вывести список из трёх наиболее популярных задач
с указанием количества запросов по ним. Если в запросах упоминаются
менее трех задач, то выведите информацию об имеющихся задачах. Если
несколько задач имеют ту же частоту встречаемости, что и третья по частоте
встречаемости задача, их тоже нужно вывести.
Пример выходных данных для приведённого выше примера входных данных:
А+В 2
Простой делитель 2
Крестики-Нолики 1
Прямоугольник 1
Показать разбор
Содержание верного ответа и указания по оцениванию
(допускаются иные формулировки ответа, не искажающие его смысла)
Программа читает все входные данные один раз, не запоминая их в массиве,
размер которого равен а составляя только список встретившихся задач и
количества запросов по каждой из них. Во время чтения данных об
очередной задаче просматривается список ранее сохраненных задач; если
она уже есть в списке, то количество запросов по ней увеличивается на 1,
иначе задача добавляется в массив упомянутых в запросах задач (при
корректных данных он не может быть больше 11). После окончания ввода
производится сортировка массивов задач и количества запросов, отданных
за них, в порядке убывания количества запросов, затем выводится список из
трёх первых задач с указанием частоты встречаемости (или весь список,
если его длина меньше трёх). Вместо сортировки можно применить и
алгоритм поиска трёх максимальных элементов в массиве. Затем выводятся
задачи, частота встречаемости которых не ниже, чем у третьей задачи.
Баллы начисляются только за программу, которая решает задачу хотя бы для
одного частного случая. Ниже приведены примеры решения задания на
Алгоритмическом языке, а также на языках Паскаль и Бейсик. Допускаются
решения, записанные на других языках программирования. При оценивании
решений на других языках программирования необходимо учитывать
особенности этих языков программирования. Так, на языке C++ при
считывании строковой переменной будет считано не все название задачи, а
только его первое слово, поэтому следует использовать функцию
getline(cin,s), аналогичная проблема возникает и в языке Си.
Примеры правильных и эффективных программ на языках
Var N, Num, i, j, t: integer;
Count: array[1..11] of integer;
s: string;
Names: array[1..11] ofstring;
Begin
Num:=0; {Число различных задач в списке запросов}
ReadLn(N); {Считываем количество запросов}for i:=1to N dobegin
ReadLn(s); {считали очередную задачу}{Осуществляем ее поиск в списке уже встретившихся}
j:=1;
while (j<=Num) and (s<>Names[j]) do j:=j+1;
{Если она найдена}if j<=Num then{Увеличиваем счетчик числа запросов}
Count[j]:=Count[j]+1elsebegin{Иначе добавляем задачу в конец списка}
Names[j]:=s;
Count[j]:=1;
Num:=Num+1endend;
{Сортируем массивы Names и Count в порядке убывания значений
массива Count}for i:=Num downto2dofor j:=2to i doif Count[j-1]<Count[j] thenbegin
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 >= 3then j := 3else j := Num;
i := 1;
while (i <= Num) and (Count[i] >= Count[j]) dobegin
WriteLn(Names[i], ' ', Count[i]);
i := i + 1;
endend.
Критерии оценки
4 баллаПрограмма работает для любых входных данных произвольного
размера
и находит ответ, не сохраняя входные данные в массиве,
размер которого соответствует числу (количеству запросов). Программа просматривает входные данные один раз, сохраняя в массиве размером 11 данные о количестве решений, поданных
для каждой из встретившихся в списке задач (
и учитывает, что
в списке их может быть
и меньше 11). Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или
неверно указан знак пунктуации, неверно написано или пропущено
зарезервированное слово языка программирования, не описана или
неверно описана переменная, применяется операция, недопустимая
для соответствующего типа данных (если одна
и та же ошибка
встречается несколько раз, то это считается за одну ошибку).
3 баллаПрограмма работает верно, но входные данные запоминаются
в массиве, размер которого соответствует числу Этот массив,
возможно, потом сортируется. Допускается наличие от одной до
трех синтаксических ошибок. Возможно, в принципиально верно
организованном вводе данных есть одна ошибка (например,
использование read вместо readln в Паскале или неверное
считывание строки в C++). Три балла также выставляется, если
в эффективной программе, удовлетворяющей критериям выставления 4 баллов, есть одна ошибка, в результате которой программа
работает неверно на некоторых наборах нетипичных входных
данных (например, все запросы относятся к одной
и той же задаче)
2 баллаПрограмма работает в целом верно, эффективно или нет, но
в реализации алгоритма содержится до двух ошибок (неверная
инициализация счётчиков – хотя в предложенных выше решениях
обнулять их не требуется; возможно, программа неверно работает,
если в списке упомянуто меньше 11 задач, выход за границу
массива, допущена ошибка в принципиально верно организованной
сортировке или алгоритме поиска минимальных элементов,
используется знак “<” вместо “<=”, “or” вместо “and”
и т. п.).
Возможно, некорректно организовано считывание входных
данных. Допускается наличие от одной до пяти синтаксических
ошибок, описанных выше.
1 баллПрограмма, возможно, неверно работает при некоторых входных
данных, но по приведённому тексту решения ясно, что
экзаменуемый понимает, из каких этапов должно состоять решение
задачи. При использовании сортировки она может быть
реализована принципиально неверно (например, вместо двух
циклов используется один), или допущена принципиальная ошибка
в поиске трёх максимальных элементов. Всего допускается до 4
различных ошибок в реализации алгоритма, в том числе описанных
в критериях присвоения двух баллов. Допускается наличие от
одной до семи синтаксических ошибок, описанных выше
0 балловЗадание не выполнено или выполнено неверно.