ABBA Game

Однажды Джейми заметил, что во многих английских словах используются только буквы A и B. Примеры таких слов включают "AB" (сокращение от abdominal), "BAA" (шум, производимый овцой), "AA" (разновидность лавы) и "ABBA".

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

• Добавьте букву А в конец строки.
• Переверните строку и добавьте букву B в конец строки. Верните "Possible" (кавычки для ясности), если есть последовательность допустимых ходов, которые превратят начальное в целевое. В противном случае верните "Impossible".

Постановка:

• Namespace: AbbaGame
• Класс: <Фамилия>
• Метод: СanObtain
• Параметры: string, string
• Возвращает: string
• Сигнатура метода: string СanObtain(string initial, string target)

Ограничения

• Длина начальной строки будет от 1 до 999 включительно.
• Длина целевой сроки будет от 2 до 1000 включительно.
• Целевая будет длиннее начальной.
• Каждый символ в начальном и каждый символ в целевом будет либо "A", либо "B".

Примеры

a) "B" "ABBA"

Возвращает: Possible

Джейми может выполнять следующие движения: Изначально строка - "B". Джейми добавляет к концу строки букву "А". Теперь строка "BA". Джейми переворачивает строку, а затем добавляет букву "B" в конец строки. Теперь строка "ABB". Джейми добавляет к концу строки букву "А". Теперь строка "ABBA". Поскольку существует последовательность ходов, которая начинается с "B" и образует строку "ABBA", ответ - "Possible".

b) "AB" "АBB"

Возвращает: Impossible

Единственные строки длины 3, которые может создать Джейми, - это "ABA" и "BAB".

c) "BBAB" "ABABABABB"

Возвращает: Impossible

d) "BBBBABABBBBBBA" "BBBBABABBABBBBBBABABBBBBBBBABAABBBAA"

Возвращает: Possible

e) "А" "BB"

Возвращает: Impossible