Для автоматизированной системы управления движением городских пассажирских автобусов требуется написать программу, которая решает следующую задачу.
На некоторой остановке в течение одного часа для каждого пассажирского автобуса фиксируется время прибытия в минутах (целое число от 0 до 60), номер маршрута (целое число), название предприятия (текстовая строка в 20 символов). Все автобусы одного маршрута принадлежат одному предприятию; одно предприятие может обслуживать несколько маршрутов. Для каждого маршрута задан плановый интервал движения в минутах (целое число от 5 до 15) — промежуток времени между моментами прихода автобусов данного маршрута. Если автобусы некоторого маршрута допускают интервал движения, превышающий плановый более чем на 2 минуты, то на предприятие начисляется по одному штрафному баллу за каждую минуту.
Необходимо вывести на экран список маршрутов и предприятий, чьи автобусы допустили нарушения, и число штрафных баллов в виде: <�номер маршрута> <�название предприятия> <�число штрафных баллов>.
Описание входных и выходных данных.
Исходные данные вводятся в компьютер в следующем порядке.
Сначала вводится число M — число маршрутов, проходящих через данную остановку, а затем вводится M строк вида: <�номер маршрута> <�интервал движения> <�название предприятия>.
Здесь <�номер маршрута> — разные целые числа в количестве М, <�интервал движения> — целые числа от 5 до 15, <�название предприятия>—строка символов, не более 20.
Далее вводится число N — число прошедших через остановку автобусов, затем вводится N строк вида <�время прибытия> <�номер маршрута>. <�Время прибытия> — целые числа от 0 до 60, вводятся в порядке неубывания, <�номер маршрута>—целые числа, каждое число обязательно совпадает с одним из номеров маршрута, введённых выше.
Пример входных данных:
3
25 15 Город
37 5 Город
28 15 Смена
8
2 25
5 37
8 28
10 37
17 25
19 37
23 28
32 25
Пример выходных данных для приведённого выше примера входных данных:
37 Город 2
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var Nmar, Id, tpm, Strf: array[1..100] of integer;
Predpr: array[1..100] of string;
M, N, i, j, t,Interv, Nm: integer;
begin
write(’ M = ’);
readln(M);
writeln(’ Nmar Id Predpr’);
for i:=1 to M do
readln(Nmar[i],Id[i],Predpr[i]);
for i:=1 to M do begin
tpm[i]:=0; Strf[i]:=0;
end;
write(’ N = ’);
readln(N);
writeln(’ t Nmar’);
for j:=1 to N do begin
readln(t,Nm);
for i:=1 to M do
if Nm = Nmar[i] then break;
Interv:=t-tpm[i]-Id[i];
if Interv > 2 then
Strf[i]:= Strf[i]+Interv;
tpm[i]:=t;
end;
for i:=1 to M do
if tpm[i]<60 then
begin
Interv:=60-tpm[i]-Id[i];
if Interv > 2 then
Strf[i]:= Strf[i]+Interv;
end;
for i:=1 to M do
write(Nmar[i],’ ’,Strf[i],’ ’,Predpr[i]);
end.