Fişierul intrare/ieşire:xmoto.in, xmoto.outSursăONI 2011, clasele 11-12
AutorTiberiu Savin, Vlad DutaAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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:

  • 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ţa

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 şi precizări

  • 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.
  • 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 ai, bi > 0
  • Pentru 50% din teste N ≤ 1.000

Exemplu

xmoto.inxmoto.out
2 150
3.0 -2.0 2.0 22000.0 60
2.0 4.0 4.0 2.0 50
1
28.800000

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content