Разбор задачи C. Городской парад
Тема: моделирование, очередь
Сложность: простая
Моделируем работу Виггама по регулированию движения платформ. На каждом шаге нужно выбрать одно из трех возможных действий:
- Отправить прибывшую платформу на площадь. Это можно сделать только в случае, когда номер прибывшей платформы равен номеру платформы, которую нужно отправить на площадь.
- Отправить первую платформу с боковой улицы на площадь. Это можно сделать только в случае, когда номер первой платформы на боковой улице равен номеру платформы, которую нужно отправить на площадь.
- Отправить прибывшую платформу на боковую улицу. Это можно сделать только в случае, если есть прибывшие платформы.
Если Виггам не может выполнить ни одно из этих действий, то печатаем сообщение "NO". Если все `N` платформ попали на площадь, печатаем сообщение "YES". Номера платформ на боковой улице нужно хранить в виде очереди.
var q,p:array[1..100] of integer;
i,pfirst,n,qfirst,qlast:integer;
begin
read(n);
for i:=1 to n do
read(p[i]);
qfirst:=1; { Индекс первого элемента в очереди }
qlast:=1; { Индекс первой свободной ячейки в очереди }
pfirst:=1; { Индекс элемента с номером прибывшей платформой }
i:=1; { Номер платформы, которую нужно отправлять на площадь }
while i<=n do
begin
if (pfirst<=n) and (p[pfirst]=i) then
begin { Отправить прибывшую платформу на площадь }
inc(pfirst);
inc(i);
end
else if (qfirst<qlast) and (q[qfirst]=i) then
begin { Отправить первую платформу с боковой улицы на площадь }
inc(qfirst);
inc(i);
end
else if (pfirst<=n) then
begin { Отправить прибывшую платформу на боковую улицу }
q[qlast]:=p[pfirst];
inc(qlast);
inc(pfirst);
end
else
begin { Нет больше платформ }
writeln('NO');
halt;
end;
end;
writeln('YES');
end.