Парадокс вероятности
Эта задача посвящена повторным подбрасываниям честной монеты, где каждый исход, H или T, имеет вероятность 1/2. Любая конкретная последовательность подбрасываний одной и той же длины, например HHH или THH, имеет одинаковую вероятность (например, 1/8 для последовательности длиной 3).
Теперь рассмотрим следующую игру для двух игроков. Каждый игрок выбирает уникальный шаблон возможных подбрасываний монеты фиксированной длины. Например, первый игрок может предсказать HHH, в то время как второй предсказывает THH. Игра начинается с того, что оба игрока наблюдают за одной и той же монетой, пока один из них не увидит свой шаблон. Например, если последовательность наблюдаемых подбрасываний начинается с HHTHTTHH..., второй игрок в нашем примере выигрывает игру, так как только что увидел шаблон THH.
Вопрос, который нас интересует, заключается в следующем: какова вероятность того, что первый игрок выиграет игру, учитывая шаблоны двух игроков? Поскольку мы подбрасываем честную монету, многие могут предположить, что шаблоны не имеют значения и что каждый игрок имеет вероятность 1/2 на победу. Однако это не так, что приводит к тому, что известно как Парадокс Вероятности.
Для некоторых шаблонов будет так, что первый игрок выигрывает с вероятностью ровно 1/2. Например, по симметрии, шаблоны TT и HH имеют равные шансы появиться первыми.
Однако снова рассмотрим наш первоначальный пример, в котором первый игрок выбирает HHH, а второй игрок выбирает THH. Для этого конкретного сопоставления единственный способ, которым первый игрок может выиграть, это если каждое из первых трех подбрасываний будет H. Если бы первое HHH появилось где-то не в начале игры, шаблон мог бы быть представлен как
...?HHH
где "..." означает, возможно, пустую начальную часть последовательности, а "?" относится к подбрасыванию непосредственно перед HHH. "?" не может быть H, как в
...HHHH
потому что тогда было бы более раннее HHH, которое завершило бы игру, подчеркнутая часть ...HHHH. Однако если предыдущее подбрасывание было T, как в
...THHH.
тогда второй игрок уже выиграл бы, увидев шаблон THH на подчеркнутом ...THHH. Таким образом, при рассмотрении шаблона HHH против THH, первый игрок выигрывает, если и только если первые три подбрасывания - это H, событие, которое происходит с вероятностью 1/8.
Еще один пример: если первый игрок выбирает TTH, а второй - THH, первый игрок выиграет с вероятностью 2/3. Ваша задача - написать программу, которая вычисляет такую вероятность.
Входные данные
Входные данные будут содержать один или несколько наборов данных, каждый в одной строке. Каждый набор данных будет состоять из двух различных шаблонов одинаковой длины, использующих только символы H и T. Общая длина шаблона будет в диапазоне от 1 до 9 включительно. Между двумя шаблонами будет пробел. Ввод заканчивается строкой, содержащей только "$".
Выходные данные
Для каждого набора данных выведите одну строку с точной вероятностью того, что первая последовательность предшествует второй в случайной последовательности подбрасываний честной монеты. Вероятность должна быть указана в виде рационального числа, сокращенного до наименьших членов, с "/" между числителем и знаменателем. Поскольку у каждого игрока есть ненулевая вероятность выигрыша, эта вероятность всегда будет строго между 0 и 1.
Предупреждение: Числитель и знаменатель для всех окончательных вероятностей могут быть выражены как 32-битные целые числа. Однако, в зависимости от вашего подхода, вам могут понадобиться 64-битные целые числа (тип long в Java или long long в C++) для некоторых промежуточных вычислений, и даже тогда вы должны быть осторожны.