Конверт

Хорошие новости! Межпланетный экспресс запускает новую услугу – теперь компания доставляет не только посылки, но и письма! Письмо - это согнутый несколько раз лист, помещённый в конверт, имеющий прозрачные окошки. Таким образом, часть листа (например, с адресом получателя) видна при закрытом конверте. Линии сгибания листа параллельны и делят лист на одинаковые прямоугольные фрагменты. Тем не менее, единственный в компании специалист по сгибанию Бендер подходит к делу безответственно, иногда допускает ошибки, и в результате напротив прозрачного окошка в конверте может оказаться не тот фрагмент листа. Гермес Конрад хочет избежать ошибок, поэтому, тщательно записывает каждый сделанный сгиб. Теперь ему нужна программа, которая по этим записям вычислит, какие именно фрагменты будут смотреть наружу после проделанных сгибаний.

Бюрократ Гермес придумал следующую систему обозначений: все возможные линии сгибов пронумерованы от 1 до n. Если мы смотрим на лицевую сторону листа и сгибаем «от себя», когда соприкасаются обратные стороны соседних фрагментов листа, а наружу смотрят лицевые стороны, такой сгиб обозначим буквой F (forward/front bend). Если сгибаем «на себя», когда соприкасаются лицевые стороны и наружу показываются обратные стороны – то буквой R (rear bend). Для фрагментов листа нумерация похожая, только с добавлением в начале буквы P, чтобы не перепутать обозначения сгибов и фрагментов: фрагменты письма пронумерованы от P₀ до P_n, где сгиб i разделяет фрагменты P_i-1, P_i. Лицевая сторона письма и любого из фрагментов обозначена F (например, P₁F), оборотная буквой R (например, P₃R)

На иллюстрации, письмо изображается со стороны (лицевая сторона изначально «смотрит» влево, а сгибы изображены как точки). Лицевая сторона обозначается тонкой линией, оборотная – толстой линией, цифрами обозначены точки сгибания, стрелками подписаны некоторые возможные варианты сгибания письма. Размеры сгиба и толщину листа считаем нулевыми, все сгибания выполняются ровно на 180°. Фрагменты после сгибания плотно прилегают друг к другу (в примере просветы после сгибания изображены только для наглядности) – так, во втором примере точки 1 и 3R совмещаются, и фрагмент P₀ может обернуться вокруг совмещённых точек. В третьем примере точки 1 и 3 также совмещаются, но при этом фрагмент P₀ не может повернуться вокруг 1 – так как ему мешают фрагменты P₂, P₃. Если Бендер попытается сделать такой сгиб, то такое письмо будет скомкано и выкинуто – это уже работа для уборщика Скраффи.

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

Входной файл INPUT.TXT содержит одну строку данных, которая начинается с двух чисел: номер наибольшего фрагмента n, 1 ≤ n ≤ 20 (таким образом, письмо имеет n точек сгиба, и n+1 фрагментов с номерами P₀, P₁ … P_n), количество проделанных сгибаний 1 ≤ m ≤ n (сгибы могут быть сделаны не в каждой возможной точке). Далее выписаны наблюдаемые сгибания через пробел, в порядке их выполнения. Если сгибать бумагу в одной точке несколько раз, то ее прочность теряется, поэтому в каждой точке сгиб производится максимум один раз.

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

В выходной файл OUTPUT.TXT выведите перечисление всех видимых фрагментов, в порядке возрастания их номеров, сначала фрагменты стороной F, потом стороны R. Либо слово SCRUFFY, если письмо было скомкано.

Примеры

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

[Обсуждение] [Все попытки] [Лучшие попытки]