Dreamoon стоит на отметке 0 на числовой прямой. Drazil отправляет ему на смартфон список команд через Wi-Fi, а Dreamoon следует им.
Каждая команда относится к одному из двух типов:
Но так как уровень сигнала Wi-Fi очень слабый, смартфон Dreamoon'а сообщает, что некоторые команды не поддаются распознаванию. Более того, Dreamoon знает, что даже некоторые из рапознанных команд могут быть неверными. Dreamoon решил выполнять каждую распознанную команду, а для нераспознанных команд бросать монетку (это значит, что он пойдёт на 1 единицу в положительном или отрицательном направлении с одинаковой вероятностью 0.5).
Вам дан изначальный список команд, которые выслал Drazil, и список, который получил Dreamoon. Какова вероятность того, что Dreamoon окажется в том положении, к которому привели бы команды Drazil'а?
В первой строке записана строка s1 — команды, которые Drazil посылает Dreamoon'у, строка состоит только из символов из набора {«+», «-»}.
Во второй строке записана строка s2 — команды, которые распознал смартфон Dreamoon'а, эта строка состоит только из символов из набора: {«+», «-», «?»}. Символом «?» обозначается нераспознанная команда.
Обе строки одинаковой длины и не превышают 10.
Выведите требуемую вероятность. Ответ будет сраниваться с относительной или абсолютной погрешностью 10 - 9.
++-+-
+-+-+
1.000000000000
+-+-
+-??
0.500000000000
+++
??-
0.000000000000
В первом примере как s1, так и s2 приведут Dreamoon'а к одной и той же позиции + 1.
Во втором примере s1 приведет Dreamoon'а к позиции 0, в то время как для s2 есть четыре варианта: {"+-++", "+-+-", "+--+", "+---"} с конечными позициями {+2, 0, 0, -2}, соответственно. Таким образом, есть 2 подходящих случая из 4, так что вероятность окончить путь в верной позиции равна 0.5.
Для третьего примера, s2 может привести только к позициям {+1, -1, -1, -3}, таким образом, вероятность окончить путь в позиции + 3 равна 0.
| Codeforces Round 272 (Div. 2) |
|---|
| Закончено |
