lt;Фамилия> <Инициалы> <номер школы>

<Фамилия> <Инициалы> <номер школы>

где <Фамилия> – строка, состоящая не более чем из 20 символов, <Инициалы> – строка, состоящая из 4-х символов (буква, точка, буква, точка), <номер школы> – не более чем двузначный номер. <Фамилия> и <Инициалы>, а также <Инициалы> и <номер школы> разделены одним пробелом. Пример входной строки:

Иванов П.С. 57

Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию, из какой школы было меньше всего участников (таких школ может быть несколько). При этом необходимо вывести информацию только по школам, пославшим хотя бы одного участника. Следует учитывать, что N>=1000.

Как правильно понимать условие?

1) на первый вопрос – как именно вводятся данные – находим ответ в самом начале условия: вроде бы «дежурная» фраза «на вход программе подаются…» означает, что данные нужно читать не из файла, а со стандартного входного потока; это, в свою очередь, значит, что можно использовать привычные операторы read (readln), предполагая, что кто-то вводит эти данные с клавиатуры вручную[1]

2) итак, сначала вводится количество записей в файле N, а затем N строк с информацией; заметим, что из всей этой информации нас интересует (в каждой строке) только номер школы, остальное можно просто отбрасывать

3) номер школы стоит после второго пробела в строке

4) «<номер школы> – не более чем двузначный номер» – крайне важная информация; собственно, только она и позволяет найти хорошее решение задачи; это значит, что школ не более 99!

5) что означает выражение «как можно более эффективная программа»?

o прежде всего, данные читаются только один раз, за один проход, нельзя «вернуться» и прочитать что-то вновь

o в программе не выполняются никакие лишние действия

o используемые алгоритмы имеют минимальную сложность (см. выше)

o расходуется минимальный возможный объем памяти; например, чтобы найти количество отрицательных элементов массива, не нужно вводить второй массив; если нам достаточно держать в памяти одну введенную строку, не нужно одновременно хранить все прочитанные строки

6) зачем нужно уточнение «N>=1000»? этим авторы задачи намекают на то, что не нужно считывать все данные в оперативную память, а потом уже их обрабатывать; основная обработка должна быть сделана сразу, в том же цикле, где читаются входные данные

7) мы будем считать, что в исходных данных нет ошибок (так принято на олимпиадах и экзаменах), иначе обработка разнообразных ошибок будет составлять основную часть программы

Решение:

1) по условию, единственная информация, которая нам нужна в итоге для вывода результата – это количество участников по каждой школе

2) так как номер школы состоит (по условию!) не более, чем из двух цифр, всего может быть не более 99 школ (с номерами от 1 до 99)

3) поэтому можно ввести массив C из 99 элементов; для всех k от 1 до 99 элемент C[k] будет ячейкой-счетчиком, в которой накапливается число участников от школы с номером k; сначала во все элементы этого массива записываются нуль (обнуление счетчиков):

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒