В командных
олимпиадах по программированию для
решения предлагается не больше 11 задач.
Команда может решать предложенные
задачи в любом порядке. Подготовленные
решения команда посылает в единую
проверяющую систему соревнований. Вам
предлагается написать эффективную, в
том числе по используемой памяти,
программу, которая будет статистически
обрабатывать пришедшие запросы, чтобы
определить наиболее популярные задачи.
Следует учитывать, что количество
запросов в списке может быть очень
велико, так как многие соревнования
проходят с использованием Интернет.
На вход программе
в первой строке подаётся количество
пришедших запросов N. В каждой из
последующих N строк записано название
задачи в виде текстовой строки. Длина
строки не превосходит 100 символов,
название может содержать буквы, цифры,
пробелы и знаки препинания. Пример
входных данных:
6
А+B
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель
Программа должна
вывести список из трёх наиболее популярных
задач с указанием количества запросов
по ним. Если в запросах упоминаются
менее трех задач, то выведите информацию
об имеющихся задачах. Если несколько
задач туже частоту встречаемости, что
и третья по частоте встречаемости
задача, их тоже нужно вывести.
Перед текстом
программы кратко опишите используемый
вами алгоритм решения задачи.
Решение:
- Краткий алгоритм решения задачи
Программа читает
все входные данные один раз, не запоминая
их в массиве,
размер которого равен N,
а составляя только список встретившихся
задач и
количества запросов по каждой
из них. Во время чтения данных об
очередной задаче просматривается список
ранее сохраненных задач; если
она уже
есть в списке, то количество запросов
по ней увеличивается на 1,
иначе задача
добавляется в массив упомянутых в
запросах задач (при
0
корректных данных
он не может быть больше 11). После окончания
ввода
3
производится сортировка массивов
задач и количества запросов, отданных
за них, в порядке убывания количества
запросов, затем выводится список из
трёх первых задач с указанием частоты
встречаемости (или весь список,
не
больше 11 задач. Команда может решать
предложенные задачи в любом если его
длина меньше трёх).
- Строим блок схему (Дракон Схему)
- По блок схеме (Дракон схеме) составляем текст программы
1 комментарий:
решение задачи
Отправить комментарий