Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: bevielis_internetas.in

Rezultatų failas: bevielis_internetas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Bevielis internetas

Gerda stovi ant skaičių ašies taške su koordinate 0. Margiris siunčia sąrašą komandų į Gerdos telefoną per bevielį tinklą, o Gerda tas komandas seka.

Kiekviena komanda yra vienos iš dviejų rūšių:

  1. \\texttt{+} reiškia, kad reikia paeiti vieną žingsnį į priekį
  2. \\texttt{-} reiškia, kad reikia paeiti vieną žingsnį atgal.

Deja, bevielis ryšys yra toks silpnas, kad Gerdos išmanusis telefonas kai kurių komandų nesugeba atpažinti, o net ir atpažintos komandos nebūtinai yra teisingos. Gerda nusprendžia laikytis tokios taisyklės: kiekvieną atpažintą komandą ji įvykdo, o kiekvienos netpažintos komandos vietoje ji meta monetą, kad nuspręstų, kuria kryptimi reikia eiti. Moneta yra ideali, t.y. galite tarti, kad abiejų pusių atsivertimo tikimybės yra lygiai 0.5.

Jums duotos dvi sekos - tai, ką siuntė Margiris, ir tai, ką gavo Gerda. Jūsų užduotis - apskaičiuoti tikimybę, kad Gerda atsidurs tiksliai ten, kur būtų atsidūrusi, jei visos komandos būtų atpažintos.

Pradiniai duomenys

Pirmoje eilutėje pateikta simbolių eilutė s_1 - komandų seka, kurią siuntė Margiris.

Antroje eilutėje pateikta simbolių eilutė s_2 - komandų seka, kurią gavo Gerda. Neatpažintos komandos žymimos simboliu \\texttt{?}.

Abiejų simbolių eilučių ilgai ilgiai neviršija 10.

Rezultatai

Jūsų programa turi išvesti vieną realųjį skaičių - ieškomą tikimybę. Atsakymas bus laikomas teisingu, jei paklaida neviršys 10^{-9}. Tiksliau tariant, jei jūsų atsakymas yra a, o tikslus atsakymas yra b, tai jūsų atsakymas bus laikomas teisingu, jei galios nelygybė \\frac{|a-b|}{max(1,b)}\\leq10^{-9}

Pavyzdžiai

Pradiniai duomenys Rezultatai 
++-+-
+-+-+
 
1.000000000000
 
+-+-
+-??
 
0.500000000000
 
+++
??-
 
0.000000000000