== include(page="template/taskheader" task_id="blindpunch") ==
In mijlocul noptii ai fost atacat de gandaci. Gandacii, foarte ordonati formeaza un sir in fata ta.
Pentru a te apara, ai $K$ papuci pe care ii poti arunca pe cate un gandac (eventual mai multi papuci pe acelasi gandac). Gandacii, foarte creativi, se prefac toti ca sunt morti pentru a te induce in eroare (fiind intuneric poti sa vezi gandacii dar nu poti sa distingi daca sunt striviti sau nu).
Din fericire, stii pentru fiecare gandac $i$ care este probabilitatea $P~i~$ ca acesta sa fie strivit printr-o aruncare de papuc (si in caz ca nu este strivit are tot probabilitatea $P~i~$ sa fie strivit din a doua aruncare etc).
În mijlocul nopţii ai fost atacat de gândaci. Gândacii, foarte ordonaţi formează un şir în faţa ta.
Pentru a te apăra, ai $K$ papuci pe care îi poţi arunca pe câte un gândac (eventual poţi arunca mai mulţi papuci pe acelaşi gândac). Gândacii, foarte creativi, se prefac toţi că sunt morţi pentru a te induce în eroare (fiind întuneric poţi să vezi gândacii dar nu poţi să distingi dacă sunt striviţi sau nu).
Din fericire, ştii pentru fiecare gândac $i$ care este probabilitatea $P{~i~}$ ca acesta să fie strivit printr-o aruncare de papuc (şi în cazul în care nu este strivit are tot probabilitatea $P{~i~}$ să fie strivit din următoarea aruncare).
Cum esti foarte obosit si urasti mai mult decat orice altcv sa se plimbe gandaci in jurul tau in timpul noptii, vrei din cele $K$ lovituri sa omori cat mai multi gandaci.
Cum eşti foarte obosit şi urăşti mai mult decât orice altceva să se plimbe gândaci în jurul tău în timpul nopţii, vrei din cele $K$ lovituri să omori cât mai mulţi gândaci.
h2. Cerinta
Dându-se $T$ astfel de scenarii, şi pentru fiecare scenariu numărul $N$ de gândaci, numărul $K$ de papuci, şi şirul $P$, unde al $i$-lea element al şirului reprezintă probabilitatea de a strivi al $i$-lea gândac dintr-o lovitură, calculează valoarea aşteptată ( _expected value_ ) de câţi gândaci poţi strivi dacă arunci în mod optim papucii.
Dandu-se $T$ astfel de scenarii, si pentru fiecare numarul $N$ de gandaci, si sirul $P$, unde al $i$-lea element reprezinta probabilitatea de-a strivi al $i$-lea gandac dintr-o lovitura, calculeaza expectedul de cati gandaci poti strivi daca arunci in mod optim papucii.
Cum esti foarte obosit si urasti mai mult decat orice altcv sa se plimbe gandaci in jurul tau in timpul noptii, vrei din cele $K$ lovituri sa omori cat mai multi gandaci.
h2. Date de intrare
Datele de intrare se citesc din fisierul $blindpunch.in$.
Prima linie contine numarul $T$, reprezentand numarul de teste.
Prima linie a fiecarui test contine numerele $N$ si $K$, reprezentand numarul de gandaci si respectiv numarul de papuci la dispozitie.
Urmatoarea linie contine sirul $P$ de lungime $N$.
Din $blindpunch.in$ se va citi pe prima linie numărul $T$, reprezentând numarul de teste.
Prima linie a fiecărui test conţine numerele $N$ şi $K$, reprezentând numărul de gândaci, respectiv numărul de papuci pe care îi ai la dispoziţie.
Urmatoarea linie conţine şirul $P$ de lungime $N$.
h2. Date de ieşire
Datele de iesire se afiseaza in fisierul $blindpunch.out$.
Afisati $T$ linii, pe linia $i$ fiind expectedul numarului total de gandaci striviti daca aruncati in mod optim papucii in al $i$-lea scenariu.
Fiecare numar trebuie afisat cu EXACT $6$ decimale, rotunjit in jos (de ex $1.23456789$ se rotunjeste la $1.234567$). Se garanteaza ca a $7$-a cifra a raspunsului este in intervalul $[0, 7]$
În $blindpunch.out$ se vor afişa $T$ linii, pe linia $i$ fiind valoarea aşteptată a numarului total de gândaci striviţi dacă arunci în mod optim papucii în al $i$-lea scenariu.
Numerele trebuie afişate cu *EXACT* $6$ zecimale, rotunjite în jos.
Se garantează că a $7$-a zecimală a raspunsului este în intervalul $[2, 7]$.
h2. Restricţii
* $1 ≤ N, K, T ≤ 10^6^$
* Suma $N$-urilor si a $K$-urilor pentru fiecare test nu va depasi $10^6^$
* $0 ≤ P~i~ ≤ 1$
* Pentru teste in valoare de $40$ de puncte, se garanteaza ca $1 ≤ suma N-urilor, suma K-urilor, T ≤ 500$.
* Pentru alte teste in valoare de $40$ de puncte, se garanteaza ca $1 ≤ suma N-urilor, suma K-urilor, T ≤ 5000$.
40p O(NK^2)
80p O(NK)
100p O((N+K)logN)
* <tex>1 \leq N, T \leq 2 \cdot 10^5</tex>
* <tex>1 \leq K \leq 10^6</tex>
* <tex>\displaystyle{\sum_{i=0}^{T}N_i} \leq 2\cdot 10^5, \displaystyle{\sum_{i=0}^{T}K_i} \leq 10^6</tex>
* <tex>0 \leq P_i \leq 1</tex>
* Pentru teste in valoare de $40$ de puncte, <tex>\displaystyle{\sum_{i=0}^{T}N_i},\ \displaystyle{\sum_{i=0}^{T}K_i},\ T \leq 500</tex>
* Pentru alte teste in valoare de $40$ de puncte, <tex>\displaystyle{\sum_{i=0}^{T}N_i}, \ \displaystyle{\sum_{i=0}^{T}K_i},\ T \leq 5000$</tex>
* Datele din input sunt date cu cel mult $9$ decimale.
* *ATENŢIE la afişarea numerelor reale!* Atunci când veţi afişa un număr asiguraţi-vă că îl afişaţi cu *EXACT* $6$ zecimale.
* Va recomandam sa faceti toate calculele folosind _long double_
h2. Exemplu
