== include(page="template/taskheader" task_id="sms") ==
Poveste şi cerinţă...
După ce a terminat de făcut curăţenie prin casă, Harry şi-a amintit că nu le-a mai dat de mult timp un mesaj prietenilor lui, Henry şi Hetty. Pentru că laptopul lui este la reparat, Harry a decis să le trimită un SMS. Mesajul pe care Harry vrea să îl trimită este compus din $N$ caractere, toate fiind cuprinse între primele $K$ litere mici ale alfabetului englez.
Telefonul lui Harry are tastatura QWERTY, însă are tastele foarte mici, astfel încât Harry nu poate fi niciodată sigur că va apăsa tasta dorită. Pentru fiecare caracter $C$ care are numărul de ordine $i$ in alfabetul englez $(1 ≤ i ≤ K)$, Harry a stabilit următoarele probabilităţi:
* $pCorect{~i~}$ - probabilitatea ca Harry să tasteze caracterul $C$;
* $pIncorect{~i~}$ - probabilitatea ca Harry să tasteze alt caracter decât $C$;
* $pBackspace{~i~}$ - probabilitatea ca Harry să tasteze Backspace şi astfel să şteargă ultimul caracter scris.
Este bine ştiut că Harry observă întotdeauna când tastează un caracter greşit, pe care îl şterge imediat apăsând tasta Backspace (pe care o va apăsa corect întotdeauna). Dacă se întamplă ca Harry să apese Backspace atunci când nu este niciun caracter scris din mesaj, nu se întâmplă nimic.
h2. Cerinta
Ştiind că orice apăsare de tastă durează exact o unitate de timp, calculaţi timpul mediu în care Harry va tasta mesajul. Timpul mediu pentru a scrie mesajul se defineşte ca fiind sumă din $T * P{~T~}$, pentru $T$ de la $0$ la $infinit$, unde $P{~T~}$ este probabilitatea de a scrie textul din exact $T$ apăsări de tastă.
h2. Date de intrare
Fişierul de intrare $sms.in$ ...
Pe prima linie a fişierului de intrare $sms.in$ se vor afla două numere naturale $N$ şi $K$, cu semnificaţia din enunţ. Pe următoarea linie se va alfa mesajul pe care Harry vrea sa îl trimită: un şir de $N$ caractere, compus doar din primele $K$ litere ale alfabetului englez. Pe următoarele $K$ linii, se vor afla probabilităţile determinate de Harry, astfel: pe linia $2+i$, $(1 ≤ i ≤ k)$ se vor afla 3 numere reale, $pCorect{~i~}$, $pIncorect{~i~}$, $pBackspace{~i~}$, cu semnificaţia din enunţ.
h2. Date de ieşire
În fişierul de ieşire $sms.out$ ...
Pe prima linie a fisierului de iesire $sms.out$ se va afişa un număr real - timpul mediu în care Harry va scrie mesajul.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1 000 000$
* $1 ≤ K ≤ 26$
* Raspunsul se va verifica cu o precizie relativa de $0.000001$.
* Pentru 40% din teste, $1 ≤ N ≤ 500$.
* Pentru orice $i, 1 ≤ i ≤ K, pCorect{~i~} + pIncorect{~i~} + pBackspace{~i~} = 1.$
h2. Exemplu
table(example). |_. sms.in |_. sms.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 1 1
a
0.5 0.0 0.5
| 2.0 |
| 3 1
aaa
0.5 0.5 0.0
| 9.0 |
| 3 1
aaa
0.5 0.25 0.25
| 10.625 |
h3. Explicaţie
...
Harry are probabilitate de $1/2^k$ să apese corect tasta $a$ după $k$ apăsări pentru prima oară. Timpul mediu de a o tasta este deci $1*1/2 + 2*1/4 + 3*1/8 + 4*1/16 + ... = 2$
== include(page="template/taskfooter" task_id="sms") ==
