Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Стоунхендж 2077

(Время: 5 сек. Память: 128 Мб Сложность: 74%)

«Крoмлех – древнее сооружение, как правило, позднего неолита или раннего бронзового века,
представляющее собой несколько поставленных вертикально в землю продолговатых камней,
образующих одну или несколько концентрических окружностей.»

(Материал из Википедии – свободной энциклопедии)

В будущем 2077-м году миру откроется заповедник «Стоунхендж 2077» – продвинутая версия легендарной английской достопримечательности. Он будет представлять из себя n камней, расположенных по кругу и образующих правильный n-угольник. Камни пронумерованы от 1 до n по часовой стрелке, если смотреть на конструкцию сверху.

Уже сейчас администрация заповедника планирует открытие первого туристического сезона. Планируется проведение экскурсий внутри заповедника. Каждая экскурсия будет соединять два различных камня. Между этими двумя камнями будет проложена прямая дорога, по которой будут ходить люди.

Ваша задача – организовать создание и закрытие экскурсии по запросам администрации. Главное правило, которое должно соблюдаться на протяжении всего времени: во избежание столкновений никакие две экскурсии не должны пересекаться или иметь общий конец. Формально, администрация будет давать вам команды двух типов:

  • «link a b» – запрос на создание экскурсии между камнями a и b (1 ≤ a, b ≤ n; a ≠ b). Если возможно создать такую экскурсию, то создать её и сообщить администрации её порядковый номер. Номера выдаются в порядке создания экскурсий, начиная с единицы. Если же создание невозможно из-за пересечения с какими-либо уже существующими экскурсиями – сообщить об ошибке и не создавать.
  • «cut k» – запрос на отмену экскурсии с порядковым номером k. Гарантируется, что на момент запроса экскурсия с таким номером существует в программе заповедника.

Входные данные

В первой строке входного файла INPUT.TXT содержатся два целых числа n – количество камней, и m – количество команд (3 ≤ n ≤ 109; 1 ≤ m ≤ 3×105). В следующих m строках содержатся команды в формате, описанном выше.

Выходные данные

В выходной файл OUTPUT.TXT для каждой операции первого типа в отдельной строке выведите «added as k», где k – номер экскурсии, если её можно проводить в данный момент, и «error», если невозможно.

Пример

INPUT.TXTOUTPUT.TXT
110 8
link 2 4
link 9 5
link 3 8
link 4 5
link 6 7
cut 1
cut 2
link 3 8
added as 1
added as 2
error
error
added as 3
added as 4

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 A. Книги
 B. Рейд-Босс
 C. Сапёр
 D. Стоунхендж 2077
 E. Новый будильник
 F. Тепло
 G. Очень длинный корень
 H. Плохой хеш
 I. Максимальное число
 J. Дроны фермера Джона

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru