Ali Lalap se joacă Xmoto pe telefonul mobil. Scopul jocului este de a parcurge cu motocicleta circuitul din Gheorgheni. Traseul este format din
N tronsoane. Consumul de benzină pentru tronsonul
i (
1 ≤ i ≤ N) este definit astfel:
ai * v + ki litri, dacă
v ≤ vi
bi * v + qi litri, dacă
v > vi,
unde
ai,
bi,
ki,
qi,
vi sunt valori constante, iar
v este viteza cu care se deplasează Ali Lalap pe acel tronson.
Pentru a nu forja motocicleta, lui Ali Lalap îi place să meargă cu viteză constantă şi ar vrea să ştie câte posibilităţi de a alege viteza cu care să parcurgă traseul există astfel încât să consume
L litri de combustibil.
Cerinţă
Calculaţi pentru câte valori distincte ale vitezei consumul total va fi de
L litri.
Date de intrare
Pe prima linie din fişierul de intrare
xmoto.in se află numerele naturale
N şi
L. Următoarele
N linii conţin fiecare cele patru numere reale
ai bi ki qi urmate de un număr întreg
vi cu semnificaţiile din enunţ.
Date de ieşire
Fişierul de ieşire
xmoto.out va conţine pe prima linie un singur număr
M, reprezentând numărul maxim de valori ale vitezei cu care parcurgând în întregime traseul se obţine un consum total de
L litri. Pe următoarele
M linii se vor afişa
M numere reale, distincte, cu 6 zecimale şi sortate crescator
w1 w2 ... wM, astfel încât dacă se parcurge traseul cu viteza
wi (
1<=i<=M) să se obţină un consum total de
L litri.
Restricţii
•
N ≤ 50 000
• Numerele reale
ai,
bi aparţin intervalului
[-100, 100]
•
-1 000 000 ≤ ki, qi ≤ 1 000 000
•
L ≤ 100 000 000
• Pe fiecare tronson consumul va fi strict pozitiv pentru orice viteză din intervalul (0, 10 000]
• Viteza maximă a motocicletei este de 10 000 km/h
• Motocicleta rulează de la început până la sfârşit cu aceeaşi viteză (nu se pierde timp cu plecarea de pe loc, nu există accelerări/frânări )
• Toate vitezele (viteza maximă, vitezele
vi, viteza care trebuie determinată) sunt exprimate în aceeaşi unitate de măsură
• Se consideră corectă orice soluţie în care vitezele diferă cu cel mult 10
-6 faţă de rezultatul corect.
• Verificarea consumului total se va face cu o precizie de 10
-6 faţă de
L.
• Se garantează că
M este finit.
Exemple
xmoto.in | xmoto.out | Explicaţii |
2 150
3.0 -2.0 2.0 22000.0 60
2.0 4.0 4.0 2.0 50
| 1
28.800000
| 28.8 ≤ 60 deci consumul pe primul tronson este x=3*28.8+2=88.4
28.8 ≤ 50 deci consumul pe al doilea tronson este y=2*28.8+4=61.6
Consumul total: x+y=88.4+61.6=150
|