| Fişierul intrare/ieşire: | eqprob.in, eqprob.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 18 |
| Autor | George Marcus | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
Vezi solutiile trimise | Statistici
Eqprob
Se da un sir de caractere S de lungime N. Se alege la intamplare A un subsir nevid al lui S si B o subsecventa nevida a lui S.
Care este probabilitatea ca A si B sa fie egale?
Date de intrare
Fişierul de intrare eqprob.in va contine pe prima linie un numar intreg T reprezentand numarul de teste. Fiecare test are urmatorul format: pe prima linie se afla un numar intreg N, lungimea sirului; pe a doua linie se afla sirul S.
Date de ieşire
În fişierul de ieşire eqprob.out se vor afla raspunsurile pentru cele T teste. Raspunsul pentru fiecare test are urmatorul format: un numar real reprezentand probabilitatea ca A si B sa fie egale, afisata cu o precizie de 12 zecimale.
Restricţii
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 50
- S contine doar litere mici ale alfabetului englez.
- Se numeste subsir de lungime K al sirului S un sir T = Si1Si2...SiK, astfel incat 1 ≤ i1 < i2 < ... < iK ≤ N.
- Se numeste subsecventa a sirului S un sir T = SiSi+1...Sj-1Sj, 1 ≤ i ≤ j ≤ N.
- Doua subsiruri se considera distincte daca cele doua siruri de indici corespunzatoare celor doua subsiruri difera prin cel putin un element. La fel si in cazul subsecventelor.
- Rezultatul va fi considerat corect daca difera fata de rezultatul corect cu cel mult 10-9.
Exemplu
| eqprob.in | eqprob.out |
|---|---|
| 3 1 x 2 aa 3 aca | 1.000000000000 0.555555555556 0.190476190476 |
Explicaţie
In testul 2, S = aa.
Exista 3 subsiruri nevide: a, a, aa.
Exista 3 subsecvente nevide: a, a, aa.
Daca alegem A = aa, probabilitatea ca A = B este 1/3.
Daca alegem A = a, probabilitatea ca A = B este 2/3.
Deci, probabilitatea totala este 1/3 * 2/3 + 1/3 * 2/3 + 1/3 * 1/3 = 5/9.
