Парадокс Ймовірності
Ця задача стосується повторних підкидань чесної монети. Кожен результат, 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++) для деяких проміжних обчислень, і навіть тоді ви повинні бути обережними.