eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

До першого випадіння High

До першого випадіння High

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Двоє гравців грають у наступну гру. Кожен з гравців називає деяку послідовність, яка складається з 0 та 1. Після цього починають підкидувати симетричну монету до тих пір, доки результати останніх кидань не співпадуть з послідовністю одного з гравців (значення 0 відповідає решці, 1 – гербу). Виграє звичайно той гравець, чия послідовність випаде раніше. Потрібно за заданими послідовностями, названими гравцями, визначити ймовірність перемоги першого гравця.

Обмеження

Послідовності, названі гравцями – не порожні і мають довжину не більшу 50. Жодна з послідовностей не є суфіксом іншої.

Вхідні дані

У першому рядку міститься послідовність першого гравця, у другому рядку – другого гравця (без пропусків).

Вихідні дані

Виведіть ймовірність того, що послідовність першого гравця випаде раніше, ніж послідовність другого гравця з точністю не менше 10^{-8}.

Приклад

Вхідні дані #1
001
110
Вихідні дані #1
0.50000000