print1584. Матрёшки АТЭС

printМатрёшки АТЭС

Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

К моменту проведения саммита АТЭС во Владивостоке было решено изготовить подарочные наборы матрёшек, по `N` штук в каждом.
Матрёшек в каждом наборе располагают в порядке убывания вместимости и нумеруют от 1 до `N`. Таким образом самая большая матрёшка получает номер 1, а самая маленькая – `N`. Для упаковки матрёшек в набор используют следующий алгоритм: за один шаг каждая матрёшка, находящаяся на четной позиции, помещается (вместе со всеми матрёшками внутри) внутрь ближайшей слева матрёшки. Эта операция продолжается до тех пор, пока все матрёшки не будут упакованы в одну.
После упаковки достаточно большого количества наборов обнаружилось, что оборудование, красящее матрёшки с номерами `X` и `Y`, сломалось, и в наборах оказались неокрашенные сувениры. Для быстрого извлечения матрёшек с этими номерами требуется восстановить часть шагов алгоритма упаковки, выполнявшихся до тех пор, пока одна из них не оказалась внутри другой.
`i`-ый шаг алгоритма описывается путём указания четырёх чисел `X_{L_i},\ X_{R_i},\ Y_{L_i},\ Y_{R_i}`, обозначающих, что после упаковки матрёшки с номером `X_{R_i}` в матрёшку с номером `X_{L_i}`, матрёшка `X` оказалась внутри `X_{L_i}`. Аналогично для матрёшки `Y`.
Последний шаг алгоритма описывается двумя числами `L_F,\ R_F` – после упаковки матрёшки с номером `R_F` в матрёшку с номером `L_F` оказалось, что матрёшки `X` и `Y` находятся внутри матрёшки `L_F`.
Входной файл содержит три целых числа – `N\ X\ Y` (`2\ ≤\ N\ ≤\ 2^30`, `1\ ≤\ X\ <\ Y\ ≤\ N`).
Выходной файл должен содержать подробный процесс упаковки матрёшек:
Каждая строка, описывающая один шаг алгоритма, кроме последней, должна содержать четыре целых числа – `X_{L_i},\ X_{R_i},\ Y_{L_i},\ Y_{R_i}` Последняя строчка должна содержать два целых числа – `L_F,\ R_F`
В случае, когда на каком-либо шаге в матрёшку ничего не упаковывается, указать, что матрёшка помещается сама в себя.

Пример ввода 1

6 2 5

Пример вывода 1

1 2  5 6
1 3  5 5
1 5

Пример ввода 2

21 9 15

Пример вывода 2

9 10  15 16
9 11  13 15
9 13
Источник: http://imcs.dvgu.ru/cats/ Школьники ACM, 2010
loading