Fişierul intrare/ieşire:	blindpunch.in, blindpunch.out	Sursă	IIOT 2019-20 Runda 1
Autor	Alexandru Petrescu	Adăugată de	Comisia IIOT 2019-20 •unibucPoli2019
Timp execuţie pe test	1.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Blind Punch

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

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.

Cerinta

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.

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.

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.

Numerele trebuie afisate cu EXACT 6 decimale, rotunjite in jos.
Se garanteaza ca a 7-a decimala a raspunsului este in intervalul [0, 7].

Restricţii

• 1 ≤ N, K, T ≤ 10⁶
• Suma N-urilor si a K-urilor pentru fiecare test nu va depasi 10⁶
• 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.
• Datele din input sunt date cu cel mult 9 decimale.
  40p O(NK^2)
  80p O(NK)
  100p O((N+K)logN)

Exemplu

Explicaţie

...

Cum se trimit solutii?