Бразилия
Бразилия
В фильме Терри Гиллиама "Бразилия" мы знакомимся с мрачным миром, которым управляет переросток из всеохватывающей бюрократической системы.
В то время как существуют некоторые его сходства с миром Оруэлла, изображенного в Девятнадцать Восемьдесят четыре, миру в Бразилии не хватает эффективности. Бюрократическая система полностью лишена функциональности, а весь мир полностью зависит от старых и плохо работающих машин.
В целом, Бразилия является фильмом, который стоит посмотреть. Изображенная во многих его сценах проблема навеяна бюрократической системой.
Вот основные положения системы:
- Существует неограниченное количество бюрократов. В нашей задаче будем нумеровать их числами от 1 до
109
. - Бюрократы обрабатывают формы. Каждой формой является лист бумаги. Каждая форма имеет ID код: целое число между 1 и
109
включительно. Может существовать несколько форм с одним ID. - В каждый момент времени каждый бюрократ имеет ноль или более форм на своем столе. Все эти формы всегда расположены в виде одной стопки.
- Постоянно жители приходят к бюрократам заполнять новые формы. Новая форма заполняется и отправляется любому бюрократу. Это бюрократ принимает форму и помещает ее на вершине своей кучи.
- Время от времени бюрократ может решить, что кипа его необработанных форм слишком велика. В этом случае он ждет, когда другой бюрократ на минутку отвлечется. Как только это произойдет, наш бюрократ берет всю свою кучу форм и помещает ее на вершину кучи ничего не подозревающего другого бюрократа (порядок форм в стопке сохраняется. Наш чиновник теперь имеет пустую таблицу).
- Ни одна из форм не обрабатывается. Никогда. Все формы постоянно циркулируют между бюрократами.
Вам следует промоделировать этот механизм. Чтобы быть более точным, следует промоделировать последовательность запросов, каждый из которых либо “бюрократ B получает новую форму F”, либо “бюрократ B1
отдает все свои формы бюрократу B2
”. Считайте, что в начале моделирования ни у кого не было ни одной формы.
Входные данные
Содержит не более 105
+ 1 строк. Каждая строка имеет один из следующих форматов:
- “**A b f**”, где b - ID бюрократа, f - ID новой формы, которая добавляется на верх кипы.
- “M
b1
b2
”, гдеb1
иb2
- ID таких бюрократов, что все формы со столаb1
переносятся на верх кипы на столеb2
(если столb1
пуст, но ничего не происходит). - “E” - завершение моделирования. Эта строка встречается только раз, она последняя на входе.
Выходные данные
Рассмотрим всех бюрократов, чьи кипы форм в конце моделирования не пусты. Для каждого из них выведите одну строку вида “id: f1
f2
... fn
”, где id - ID бюрократа, от f1
до fn
- ID форм в его куче сверху вниз. ID бюрократов следует выводить в возрастающем виде. Пробелы следует выводить строго в тех местах где они должны быть.
Пример
Рассмотрим порядок выполнения запросов в тесте 1:
- Бюрократ 10 получил новую форму 47.
- Бюрократ 10 отдал все свои формы (1 форму) бюрократу 20.
- Бюрократ 20 отдал все свои формы (1 форму) обратно бюрократу 10.
- Бюрократ 20 отдал все свои формы (0 форм) бюрократу 10.
- Бюрократ 20 получил новую форму 42.
- Бюрократ 20 получил новую форму 43.
- Бюрократ 20 отдал все свои формы (2 формы) бюрократу 10.
A 10 47 M 10 20 M 20 10 M 20 10 A 20 42 A 20 43 M 20 10 E
10: 43 42 47
A 1234 111111111 A 567 222222222 E
567: 222222222 1234: 111111111