Xmoto

xmoto

== include(page="template/taskheader" task_id="xmoto") ==

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:
 
* $a$~i~ $* v + k$~i~ litri, dacă $v ≤ v$~i~
* $b$~i~ $* v + q$~i~ litri, dacă $v > v$~i~
 
unde $a$~i~, $b$~i~, $k$~i~, $q$~i~, $v$~i~ 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.
 
h2. Cerinţa
 
Calculaţi pentru câte valori distincte ale vitezei consumul total va fi de $L$ litri.

Poveste şi cerinţă...

h2. 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 $a$~i~, $b$~i~, $k$~i~, $q$~i~ urmate de un număr întreg $v$~i~ cu semnificaţiile din enunţ.

Fişierul de intrare $xmoto.in$ ...

h2. 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 $w$~1~, $w$~2~, ... $w$~M~, astfel încât dacă se parcurge traseul cu viteza $w$~i~ ( $1 ≤ i ≤ M$ ) să se obţină un consum total de $L$ litri.

În fişierul de ieşire $xmoto.out$ ...

h2. Restricţii şi precizări

h2. Restricţii

* $N ≤ 50.000$
* numerele reale $a$~i~, $b$~i~ aparţin intervalului $[-100, 100]$
* $-1.000.000 ≤ k$~i~$, q$~i~ $≤ 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 $v$~i~, 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.
* Se garantează că $M$ este finit.
* Pentru determinarea corecta a lui $M$ fără a calcula corect si cele $M$ viteze se va obtine $50%$ din punctajul pe test
* Pentru $10%$ din teste $N = 1$
* Pentru $25%$ din teste $a$~i~$, b$~i~ $> 0$
* Pentru $50%$ din teste $N ≤ 1.000$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. xmoto.in |_. xmoto.out |

| 2 150
3.0 -2.0 2.0 22000.0 60
2.0 4.0 4.0 2.0 50
| 1
28.800000

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

$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$

...

== include(page="template/taskfooter" task_id="xmoto") ==

5617