Fişierul intrare/ieşire:lacapatullumii.in, lacapatullumii.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.005 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

C. La capatul lumii

Dupa ce au reusit cu greu sa scape din satul lor natal, piratii ajung pe o insula pustie, la capatul lumii. Aceasta insula nu numai ca nu se afla pe nicio harta si nu a mai fost gasita de nimeni in trecut, dar este si una magica, avand in mijlocul ei un rau pe care poate curge fie apa, fie rom. Pentru a-si putea alege bautura pe care o vor avea la dispozitie pentru eternitate, zeul insulei, marele Elf, ii supune la o provocare. Le ofera acestora un cufar care contine n monede magice si le spune: "Fiecare dintre aceste n monede are o probabilitate pi de a pica pajura atunci cand este aruncata. Aveti dreptul sa extrageti o singura moneda, pe care sa o aruncati apoi de exact k ori. Pe capacul cufarului se afla un numar m. Voi trebuie sa imi spuneti , daca as arunca moneda pe care ati extras-o voi de exact m ori, care este numarul de pajure la care ar trebui sa ma astept sa pice de-a lungul acestor aruncari!". Piratii isi dau seama ca daca nu vor reusi sa rezolve aceasta problema, sansele lor de a supravietui fara bautura lor de suflet sunt minime, asa ca se hotarasc sa va ceara ajutorul. Stiind ca acestia extrag cu o probabilitate uniforma una dintre monedele din cufar si dandu-vi-se numarul de monede, probabilitatea fiecarei monede in parte de a pica pajura, numarul de aruncari pe care le au la dispozitie, ce a picat in urma fiecarei aruncari in parte si numarul m, voi trebuie sa le spuneti care este valoarea asteptata de marele Elf.

Date de intrare

Fişierul de intrare lacapatullumii.in contine pe prima linie numarul t, reprezentand numarul de teste pentru care trebuie sa gasiti raspunsul. Fiecare test are urmatoarea configuratie: prima linie contine un numar natural n, cu semnificatia din enunt, a doua linie contine n numere reale, cu exact trei zecimale, numarul i reprezentand probabilitatea de a pica pajura daca moneda i este aruncata, a treia linie contine numarul k, cu semnificatia din enunt, a patra linie contine un sir de exact k caractere, caracterul de la pozitia i fiind 1 in cazul in care in urma aruncarii cu numarul i a picat pajura si 0 in caz contrar, a cincea linie contine numarul m, cu semnificatia din enunt.

Date de ieşire

În fişierul de ieşire lacapatullumii.out se vor afisa pe linii diferite raspunsurile la cele t teste in ordinea in care acestea au fost citite.

Restricţii

  • 1 ≤ t ≤ 10
  • 1 ≤ n ≤ 10.000
  • 0 ≤ pi ≤ 1
  • 0 ≤ k ≤ 1.000
  • 0 ≤ m ≤ 108
  • Raspunsul este considerat corect daca difera de cel al comisiei cu o toleranta de cel mult 0.000001.
  • Se garanteaza ca cele k aruncari au fost notate exact in ordinea in care s-au intamplat in realitate!

Exemplu

lacapatullumii.inlacapatullumii.out
1
3
0.666 0.500 0.334
2
01
100
50.000000
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?