Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2063. Склад Оби-Вана Кеноби
СпискиОлимпиадные задачи на русском языке
| 03/07/2014 | Лето 2014 - 04 (B) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Оби-Ван Кеноби – один из последних представителей ордена рыцарей джедаев. Оби-Ван Кеноби родом
с планеты Стьюджон, где абсолютно все жители чтут порядок, и Оби-Ван Кеноби – не исключение.
Во всех эпизодах "Звездных войн" Оби-Ван Кеноби орудует синим световым мечом, но мало кто знает,
что на самом деле у него их много, причем все мечи Кеноби пронумерованы. Оби-Ван Кеноби хранит
все свои мечи на очень длинном столе. Когда он хочет вооружиться, то он берет самый правый меч со стола,
и идет по своим делам. Оби-Ван Кеноби орудует взятым мечом пока не потеряет или не сломает его.
Иногда кто-нибудь дарит Оби-Вану Кеноби новый меч, и тогда он просто кладет его на стол справа к тем, что
уже лежат там. Но самое страшное случается тогда, когда к столу подходит мама Оби-Вана Кеноби.
Мама тоже житель планеты Стьюджон, и поэтому она всегда возмущается, что мечи лежат неупорядоченно.
Чтобы исправить это, она забирает всю левую половину мечей (если мечей на столе было нечетное количество, то мама
забирает наибольшее целое число мечей, меньшее половины их общего количества) и начинает их подкладывать справа к оставшимся.
Причем сначала она кладет меч, который изначально был самым левым, потом правее от него кладет второй меч
и так далее.
Определите, в каком порядке лежат мечи у Оби-Вану Кеноби на данный момент. У каждого меча есть свой личный номер,
который известен только Оби-Вану Кеноби. Ну и, конечно, вам.
В первой строке входного файла дано натуральное числа `n` – количество изменений, произошедших на столе
(`1\ ≤\ n\ ≤\ 10^6`).
В следующих `n` строках заданы описания изменений в следующем формате:
- если строка начинается со слова add, то в той же строке через пробел находится число `x` (`1\ ≤\ x\ ≤\ n`) – личный номер меча, подаренного Оби-Вану Кеноби. Гарантируется, что мечей с таким номером Оби-Вану Кеноби раньше не дарили и больше не подарят.
- если строка содержит единственное слово take, то это обозначает, что Оби-Ван Кеноби забрал самый правый меч со стола с собой. Если на столе не было мечей, то ничего не произошло.
- если же строка содержит единственное слово mum!, то это обозначает, что к столу подошла мама и навела порядок. Если на столе было меньше двух мечей, то ничего не произошло.
Изначально стол был пуст.
В первой строке выходного файла выведите число `k` – количество мечей, лежащих на данный момент на столе у Оби-Вана Кеноби.
В следующей строке выведите `k` чисел через пробел – личные номера мечей, лежащих на столе, в том порядке, в котором они на нем лежат (слева направо). Если `k=0`, то вторую строку не выводить.
Пример ввода
8 add 1 add 2 add 4 add 3 add 5 add 8 take mum!
Пример вывода
5 4 3 5 1 2
После выполнения операций add и take на столе будет лежать пять мечей в следующем порядке: 1 2 4 3 5. После
чего придет мама Оби-Вана Кеноби, возьмет мечи с номерами 1 и 2, и положит их права от оставшихся трех мечей на столе.
Источник: neerc.ifmo.ru/school