demon998

17.04.2021 01:55

Информатика

Есть ответ 👍

E. зоопарк глеба ограничение времени
1 секунда ограничение памяти 256mb ввод стандартный ввод или input.txt вывод стандартный вывод или output.txt
недавно глеб открыл свой зоопарк. по лучшим мировым традициям он имеет форму круга, впрочем это не важно. важно то, что он взял вас туда начальником охраны. казалось бы все началось так хорошо, но именно в вашу первую смену кто-то открыл все клетки и животные разбежались по всему зоопарку. перед вами встала поймать всех животных в ловушки, чтобы потом вернуть каждого в свою клетку. в зоопарке n животных различных животных одного из 26 видов. каждый вид обозначается своей буквой от 'a' до 'z'. под каждый из них есть свой тип ловушки. ловушки обозначаются латинскими заглавными буквами. к сожалению, почти все животные враждуют между собой в природе, поэтому ни одно животное не станет переходить дорогу животному своего или другого вида из-за инстинкта самосохранения. зоопарк по периметру обнесен колючей проволкой, поэтому животные не могут ходить вдоль забора. с камер, удалось выяснить, где находятся все животные. умная система поддержки жизнедеятельности зоопарка уже просканировала зоопарк и вывела типы всех животных и ловушек в том порядке, в котором они видны из центра зоопарка против часовой стрелки. получилось так, что все животные и все ловушки находятся около забора, то есть можно считать, что путь любого животного начинается в одной из точек окружности и заканчивается в точке, где находится ловушка для животных этого вида - тоже точка на окружности. вы хотите понять, могут ли животные придти в свою ловушку так, чтобы их путь не пересекался ни с одним другим. если да, выведите какую-нибудь из схем поимки животных.
формат ввода на вход подается строчка из 2 ⋅ n, (n ≤ 1) символов латинского алфавита, где маленькая буква - животное, а большая - ловушка. гарантируется, что ловушек каждого типа столько же, сколько и представителей данного вида животных в зоопарке.
формат вывода требуется вывести "impossible", если решения не существует или "possible", если можно загнать всех животных в свои ловушки так, чтобы их пути не пересекались. если это возможно, то для каждой ловушки в порядке обхода требуется вывести индекс животного, которое будет поймано в ней. индексом животного называется его порядковый номер среди животных в общем списке животных и ловушек.
пример 1
ввод abba вывод possible 2 1
пример 2 ввод abab вывод impossible
примечания первый пример: животное b идёт в ловушку b, а животное a ловится в ловушку a. их пути не пересекаются, поэтому их возможно поймать. второй пример: пути животных в любом случае пересекаются, поэтому поймать их невозможно.
в паскаль