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.
Se garanteaza ca raspunsul pentru un scenariu poate fi scris sub forma P / Q. In output afisati P * Q-1 MOD 1e9+7
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.
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
...
