Fişierul intrare/ieşire:eqprob.in, eqprob.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorGeorge MarcusAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test1 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.ineqprob.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?