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. их пути не пересекаются, поэтому их возможно поймать. второй пример: пути животных в любом случае пересекаются, поэтому поймать их невозможно.
в паскаль
32768
Объяснение:
Данная незамысловатая функция Excel VBA формирует строку, согласно условию.
Function replstr(str As String, n As Integer) As String
Dim a(1 To 3), b(1 To 3) As String, i, j As Integer
a(1) = "A": a(2) = "B": a(3) = "AB"
b(1) = "AB": b(2) = "AB": b(3) = "A"
For i = 1 To n
j = (i - 1) Mod 3 + 1
str = Replace(str, a(j), b(j))
Next
replstr = str
End Function
Аргументы функции:
1) Исходная строка (а данном случае “AA”)
2) Число операций с исходной строкой
Значение первых 13 операций:
=replstr("AA";1) ABAB
=replstr("AA";2) AABAAB
=replstr("AA";3)
=replstr("AA";4) ABABABAB
=replstr("AA";5) AABAABAABAAB
=replstr("AA";6)
=replstr("AA";7) ABABABABABABABAB
=replstr("AA";8) AABAABAABAABAABAABAABAAB
=replstr("AA";9)
=replstr("AA";10)
=replstr("AA";11)
=replstr("AA";12)
=replstr("AA";13)
Для подсчета символов “A” в строке, используем еще одну функцию:
Function chrcount(str1 As String, str2 As String) As Integer
Dim str() As String
str = Split(str1, str2)
chrcount = UBound(str, 1)
End Function
Аргументы функции:
1) Cтрока
2) Символ (последовательность символов), число которых требуется найти
Например, результатом использования функции =chrcount(replstr("AA";20);"A") в ячейке Excel будет число 256
Используя описанные функции, посчитаем символы “A”в первых 13 строках
Номер операции (i) Число символов “A” в строке
1 2
2 4
3 4
4 4
5 8
6 8
7 8
8 16
9 16
10 16
11 32
12 32
13 32
Как видно из таблицы, число символов в строке образует числовую последовательность 2^1; 2^2; 2^2; 2^2; 2^3; 2^3; 2^3; … 2^([(i-2)/3]+2)
Таким образом, мы получили формулу для вычисления числа символов “A”в строке по номеру операции.
Соответственно, 2^([(43-2)/3]+2) = 32768