Fişierul intrare/ieşire:orase2.in, orase2.outSursăONI 2017, clasa a 9-a
AutorAlexandru VeleaAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.8 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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ă.

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.

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.

Date de ieşire

Fişierul de ieşire orase.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.

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

Exemplu

orase2.inorase2.outExplicaţii
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?