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

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

HotLog


 

Зоопарк Глеба

(Время: 1 сек. Память: 16 Мб Сложность: 46%)

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

В зоопарке n различных животных одного из 26 видов. Каждый вид обозначается своей буквой от 'a' до 'z'. Под каждый из них есть свой тип ловушки. Ловушки обозначаются латинскими заглавными буквами. К сожалению, почти все животные враждуют между собой в природе, поэтому ни одно животное не станет переходить дорогу животному своего или другого вида из-за инстинкта самосохранения.

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

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

Вы хотите понять, могут ли животные придти в свою ловушку так, чтобы их путь не пересекался ни с одним другим. Если да, выведите какую-нибудь из схем поимки животных.

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

Входной файл INPUT.TXT содержит строку, состоящую из 2×n символов латинского алфавита, где маленькая буква - животное, а большая - ловушка. Здесь n (1 ≤ n ≤ 10000) - количество животных и ловушек. Гарантируется, что ловушек каждого типа столько же, сколько и представителей данного вида животных в зоопарке.

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

В выходной файл OUTPUT.TXT выведите "Impossible", если решения не существует или "Possible", если можно загнать всех животных в свои ловушки так, чтобы их пути не пересекались.

Если это возможно, то для каждой ловушки в порядке обхода требуется вывести индекс животного, которое будет поймано в ней. Индексом животного называется его порядковый номер среди животных в общем списке животных и ловушек.

Примеры

INPUT.TXTOUTPUT.TXT
1ABbaPossible
2 1
2ABabImpossible

Пояснения к примерам

В первом примере животное b идёт в ловушку B, а животное a ловится в ловушку A. Их пути не пересекаются, поэтому их возможно поймать.

Во втором примере пути животных в любом случае пересекаются, поэтому поймать их невозможно.


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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2005 / 2006
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 A. Ограда
 B. Опасные перекрестки
 C. Странная Лотерея
 D. Пароль
 E. Зоопарк Глеба

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