Fişierul intrare/ieşire:diapazon.in, diapazon.outSursăAlgoritmiada 2016, Runda Finala, Seniori
AutorAndrei Popa, Eugenie Daniel PosdarascuAdăugată deandreiiiiPopa Andrei andreiiii
Timp execuţie pe test2.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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, C), max(B, 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: Left, Right, P, Q, reprezentand un diapazon [Left, Right] 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 < Left ≤ Right ≤ 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.indiapazon.out
5
35 64 58 873
41 70 407 729
18 90 165 628
10 57 33 104
60 69 152 466
779316733

Raspunsul este aproximativ 49.813963.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?