== include(page="template/taskheader" task_id="lacapatullumii") ==
Poveste şi cerinţă...
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 $p[~i~]$ 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.
h2. Date de intrare
Fişierul de intrare $lacapatullumii.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $lacapatullumii.out$ ...
Î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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ t ≤ 10$
* $1 ≤ n ≤ 10.000$
* $0 ≤ p[~i~] ≤ 1$
* $0 ≤ k ≤ 1.000$
* $0 ≤ m ≤ 10^8^$
* 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!
h2. Exemplu
table(example). |_. lacapatullumii.in |_. lacapatullumii.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| $1$
$3$
$0.666 0.500 0.334$
$2$
$01$
$100$
| $50.000000$
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="lacapatullumii") ==
== include(page="template/taskfooter" task_id="lacapatullumii") ==
