== include(page="template/taskheader" task_id="sms") ==
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$ în 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. Cerință
Ș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ă.
Poveste și cerință...
h2. Date de intrare
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ț.
Fișierul de intrare $sms.in$ ...
h2. Date de ieșire
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.
În fișierul de ieșire $sms.out$ ...
h2. Restricții
* $1 ≤ N ≤ 1 000 000$
* $1 ≤ K ≤ 26$
* Răspunsul se va verifica cu o precizie relativă de $0.000001$.
* Pentru $40%$ din teste, $1 ≤ N ≤ 500$.
* Pentru orice [$i$], $1 ≤ i ≤ K$, avem egalitatea $pCorect[~i~] + pIncorect[~i~] + pBackspace[~i~] = 1$.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. sms.in |_. sms.out |_. Explicație |
| 1 1
a
0.5 0.0 0.5
| 2.0
| 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
|
| 3 1
aaa
0.5 0.5 0.0
| 9.0
| -
|
| 3 1
aaa
0.5 0.25 0.25
| 10.625
| -
|
|_. sms.in |_. sms.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="sms") ==
== include(page="template/taskfooter" task_id="sms") ==
