На вход программе поступают сведения о заводах, подающих заявку на участие в некотором государственном тендере. Требуется написать как можно более эффективную программу, которая будет выводить на экран информацию о том, из какого региона было меньше всего заявок (таких регионов может быть несколько). При этом необходимо вывести информацию только по тем регионам, в которых есть завод, подавший заявку.
Описание входных и выходных данных.
В первой строке сообщается количество заявок N, каждая из следующих N строк имеет формат <�Название Завода> <�Номер Лицензии Завода> <�Номер региона>, где <�Название Завода>—строка, состоящая не более чем из 50 символов, <�Номер Лицензии Завода> — шестизначное число, <�Номер региона>— не более чем двузначное натуральное число. <�Название Завода> и <�Номер Лицензии Завода>, а также <�Номер Лицензии Завода> и <�Номер региона> разделены одним пробелом.
Пример входных данных:
Ростсельмаш 023398 61
Спринт 342901 77
Рубин 034221 61
Армалит 822145 93
Пример выходных данных:
регион(ы) с наименьшим числом заявок:
77
93
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N заявках.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Программа читает все входные данные один раз, не запоминая их в массиве, а составляя только список встретившихся регионов и количество заявок по каждому из этих регионов, которое хранится в массиве cnt. Если при обработке данных находится регион, в котором несколько заводов подают заявку, то программа каждый раз автоматически увеличивает количество заявок от региона на 1. После окончания обработки данных программа производит поиск самого низкого числа заявок.
После нахождения самого низкого числа заявок программа проверяет, сколько всего имеется регионов с таким же количеством заявок. В конце выводятся коды регионов с самым низким числом заявок.
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var cnt: array[1..99] of integer;
c: char; i, r, N, min: integer; f: boolean;
begin
for i := 1 to 99 do cnt[i] := 0;
readln(N); {считано количество заявок}
for i := 1 to N do
begin
repeat
read(c);
until c = ’ ’; {считано название завода}
repeat
read(c);
until c = ’ ’; {считан номер лицензии завода}
readln(r);
cnt[r] := cnt[r] + 1
end;
min := 0;
f := true;
{производим поиск минимального элемента в массиве cnt}
for i := 1 to 99 do begin
if (cnt[i] < min) and (cnt[i] <> 0) then
min := cnt[i];
if f and (cnt[i] <> 0) then begin
min := cnt[i];
f := false
end
end;
{выводим коды регионов с наименьшим количеством заявок}
writeln(’регион(ы) с наименьшим числом заявок:’)
for i := 1 to 99 do
if cnt[i] = min then
writeln(i)
end.