В ювелирных магазинах продаются изделия четырёх категорий: A, B, С и D. В городе N был проведён мониторинг цен ювелирных изделий в различных магазинах. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять для каждой категории ювелирных изделий, сколько магазинов продают его дешевле всего.
Описание входных и выходных данных.
На вход программе в первой строке подаётся число данных N о стоимости ювелирных изделий. В каждой из последующих N строк находится информация в следующем формате: <�Компания> <�Магазин> <�Категория> <�Цена>, где <�Компания> — строка, состоящая не более чем из 20 символов без пробелов, <�Магазин>—строка, состоящая не более чем из 20 символов без пробелов, <�Категория>—одна из букв—A, B, C или D, <�Цена>—целое число в диапазоне от 1000 до 500 000, обозначающее стоимость одного изделия в рублях. <�Компания> и <�Магазин>, <�Магазин> и <�Категория>, а также <�Категория> и <�Цена> разделены ровно одним пробелом.
Пример входных данных:
5
Кристалл Адамас С 30000
Кристалл Блеск С 28000
Красота Элегант С 28000
Красота Бриллиант А 5000
Шик Классика А 4000
Кристалл Адамас В 10000
Программа должна выводить через пробел 4 числа— количество магазинов, продающих дешевле всего изделия категории A, B, C и D соответственно. Если ювелирное изделие какой-то категории нигде не продаётся, то следует вывести 0.
Пример выходных данных:
1 1 2 0
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N изделиях.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Во время чтения данных определяются минимальная цена ювелирных изделий каждой категории и количество магазинов, продающих изделия по этой цене. Для этого используются 8 переменных или соответствующие массивы.
Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, когда для каждой категории ювелирных изделий минимальная цена отмечена ровно в одном магазине).
Пример правильной и эффективной программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var min, kcenkat: array[’A’..’D’] of longint;
c, i, k: char;
j, N, b: integer;
begin
for i:=’A’ to ’D’ do begin
min[i]:=500000;
kcenkat [i]:=0; end;
readln(N);
for j:=1 to N do
begin
repeat
read(c);
until c=’ ’; {считана компания}
repeat
read(c);
until c=’ ’; {считана категория}
readln(k,b);
if min[k]>b then
begin
min[k]:=b; kcenkat[k]:=1
end else
if min[k] = b then kcenkat[k]:= kcenkat[k]+1;
end;
{если ювелирных изделий какой-то категории не было, kcenkat[k] осталось равным 0}
for i:=’A’ to ’D’ do write(kcenkat[i],’ ’)
end.