Задача #116

Два игрока, Петя и Ваня играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого. Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из заданных слов. Первый ход делает Петя. Выигрывает тот, кто первый составит слово из заданного набора.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Из букв «А» и «Б» составляются две символьные последовательности (два слова). Первое слово длиною 3 символа, второе длиною 6 символов.

Для игры, описанной в задании 19, определите, какое количество различных пар слов можно составить, чтобы всегда выигрывал Ваня, независимо от того, как будет ходить Петя?

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