Revizia anterioară Revizia următoare
| 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.
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]
Restricţii
- 1 ≤ N, K, T ≤ 106
- 0 ≤ P~i~ ≤ 1
- Pentru teste in valoare de 40 de puncte, se garanteaza ca 1 ≤ N, K, T ≤ 500.
- Pentru alte teste in valoare de 40 de puncte, se garanteaza ca 1 ≤ N, K, T ≤ 5000.
40p O(NK^2)
80p O(NK)
100p O((N+K)logN)
Exemplu
| blindpunch.in | blindpunch.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
