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
În continuare, vom folosi cuvântul "diapazon" ca sinonim pentru termenul de "interval". De ce? Fiindcă este distractiv.
Se dau N diapazoane [Left[i], Right[i]] numerotate de la 1 la N. Diapazonul i se afla la inaltimea N - i. Primul diapazon, cel mai de sus incepe sa cada. Toate celelalte sunt fixe. Daca pe parcursul caderii, diapazonul 1 atinge un alt diapazon j cel putin intr-un punct, atunci se va reuni cu acel diapazon cu probabilitate de P[j] / Q[j]. Din reuniunea a două diapazoane [A, B] şi [C, D] se obţine diapazonul [min(A, B), max(C, D)]. Se cere să se afle care este lungimea medie aşteptată a diapazonului cu numărul 1 la finalul căderii (i.e după ce a ajuns la o înălţime strict mai mică decât 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
...
