lacapatullumii

La capatul lumii

== include(page="template/taskheader" task_id="lacapatullumii") ==

Se considera n monede, fiecare avand probabilitatea Pi sa pice cap. Stiind ca s-a extras cu random una din cele n monede, a fost aruncata de k ori si s-a notat ce a picat de fiecare data, se cere sa se afle expected value de numarul de capuri care vor pica daca s-ar arunca aceeasi moneda de inca m ori.

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$ contine pe prima linie t, reprezentand numarul de teste. Pentru fiecare test in parte, prima linie contine un numar natural n. A doua linie contine n probabilitati, fiecare avand exact 3 zecimale dupa virgula. Urmatoarele 2 linii contin k si un sir de lungime k care contine numai 0 si 1, 0 inseamnand ca a picat pajura si 1 insemnand ca a picat cap. Ultima linie din fisier contine un singur numar, m.

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$ trebuiesc afisate raspunsurile pentru fiecare test pe linii separate.

Î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

* $... ≤ ... ≤ ...$
n <= 10.000
m <= 100.000.000
k <= 1.000

* $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 |

| 1
  3
  0.666 0.500 0.334
  2
  01
  100
| 50

| $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") ==