Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | diapazon.in, diapazon.out | Sursă | Algoritmiada 2016, Runda Finala, Seniori |
| Autor | Andrei Popa, Eugenie Daniel Posdarascu | Adăugată de |  Popa Andrei •andreiiii |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Diapazon
Se dau N diapazoane [A[i], B[i]] numerotate de la 1 la N. Diapazonul i se afla la inaltimea N - i. Primul diapazon, cel mai de sus incepe sa cada. Daca pe parcursul caderii se atinge un alt diapazon j cel putin intr-un punct, atunci se poate uni cu acel diapazon cu probabilitate de P[j]/Q[j]. A se uni inseamna ca devine [min(A[i], A[j]), max(B[i], B[j])]. Sa se afle care este lungimea in medie a intervalului final (dupa ce ajunge mai jos de toate celelalte diapazoane).
Date de intrare
Fişierul de intrare diapazon.in contine cele pe prima linie numarul N. Pe fiecare dintre urmatoarele N linii este descris cate un diapazon prin patru numere intregi: A, B, P, Q, reprezentand un diapazon [A, B] care are probabilitate P/Q sa se uneasca cu diapazonul care cade.
Date de ieşire
În fişierul de ieşire diapazon.out trebuie sa contina pe prima linie un numar natural X < 1.000.000.007. Daca raspunsul este un numar rational U/V, atunci X are proprietatea X * V ≡ U (mod 1.000.000.007).
Restricţii
- 0 < P < Q ≤ 1.000
- 0 < A ≤ B ≤ 1.000.000
- Pentru teste in valoare de 20 puncte N ≤ 200
- Pentru teste in valoare de 60 puncte N ≤ 2.000
- Pentru teste in valoare de 100 puncte N ≤ 100.000
Exemplu
| diapazon.in | diapazon.out |
|---|---|
| 5 35 64 58 873 41 70 407 729 18 90 165 628 10 57 33 104 60 69 152 466 | 779316733 |
Explicaţie
...
