Diferențe pentru problema/orase2 între reviziile #2 si #1

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

În tărâmul Jupânului există N + 1 orașe. Acestea au fost construite în linie dreaptă, începând cu cel în care este casa Jupânului. Între oricare 2 orașe consecutive s-a construit câte un drum. Pentru fiecare drum, se cunoaște lungimea lui, exprimată în metri și viteza cu care se poate parcurge, exprimată în metri pe secundă.
 
h2. Cerințe
 
Jupânul trebuie să ajungă din orașul 0 în orașul N.
Acesta știe că poate îmbunătăți un drum, mărindu-i viteza de la V metri pe secundă la V + 1 metri pe secundă, cu costul de 1 dolar. Acesta poate îmbunătăți un drum de mai multe ori.
Jupânul are un buget de X dolari și ar vrea să-i folosească pentru a micșora timpul în care ajunge din orașul 0 în orașul N.

Poveste și cerință...

h2. Date de intrare

Fișierul de intrare $orase2.in$ are următoarea structură:
 
Pe prima linie se află numărul T, reprezentând tipul de restricții pe care îl respectă testul.
Pe a doua linie, se află 2 numere naturale N și X.
Pe a treia linie se află N numere naturale, al i-lea număr reprezentând distanța între orașele i–1 și i.
Pe a patra linie se află N numere naturale, al i-lea număr reprezentând viteza între orașele i–1 și i.

Fișierul de intrare $orase2.in$ ...

h2. Date de ieșire

Fișierul de ieșire $orase2.out$ va conține pe prima linie un număr natural R ce reprezintă partea întreagă a timpului minim de parcurgere a distanței dintre orașul 0 și orașul N.

În fișierul de ieșire $orase2.out$ ...

h2. Restricții
* $... ≤ ... ≤ ...$

* 1 ≤ N ≤ 5 * 104
* 1 ≤ X ≤ 107
* lungimea drumului dintre oricare 2 orașe este un număr natural din intervalul [1, 104]
* viteza inițială dintre oricare 2 orașe consecutive este un număr natural din intervalul [1, 104]
* pentru 5% din punctaj N ≤ 10 și X ≤ 10
* pentru alte 10% din punctaj N ≤ 103 și X ≤ 103
* pentru alte 15% din punctaj 1 ≤ N ≤ 5∙104, 1 ≤ X ≤ 104, distanțele sunt mai mici decât 200 și se garantează că vitezele finale vor fi mai mici sau egale decât 1000
* pentru alte 20% din punctaj 1 ≤ N ≤ 5∙104, 1 ≤ X ≤ 107 și toate distanțele sunt egale
* pentru restul de 50% din punctaj 1 ≤ N ≤ 5∙104 și 1 ≤ X ≤ 107

h2. Exemplu
table(example).

|_. orase2.in |_. orase2.out |_. Explicatii |
| 1
3 5
5 3 7
2 1 4
| 3
| Timpul minim este 3.65, iar rezultatul este
[3.65]=3
Vitezele finale vor fi 4, 3, 5
5 / 4 + 3 / 3 + 7 / 5 = 3.65
|
|1
4 6
3 8 10 5
4 3 7 3
| 4
| Timpul minim este 4.321, iar rezultatul este
[4.321]=4
Vitezele finale vor fi 4, 7, 7, 5
3 / 4 + 8 / 7 + 10 / 7 + 5 / 5 = 4.32142857
|
| 1
5 6
2 5 3 2 4
5 1 2 1 3
| 4
| Timpul minim este 4.65, iar rezultatul este
[4.65]=4
Vitezele finale vor fi 5, 4, 3, 3, 3
2 / 5 + 5 / 4 + 3 / 3 + 2 / 3 + 4 / 3 = 4.65
|

|_. orase2.in |_. orase2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
 
h3. Explicație
...

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