Fişierul intrare/ieşire:calatorie.in, calatorie.outSursăHappy Coding 2
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.35 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Calatorie interplanetara

O nava spatiala trebuie sa calatoreasca de la planeta 1 la planeta 2, apoi de la planeta 2 la planeta 3 si tot asa pana cand ajunge la planeta N. Cand calatoreste de la planeta K la planeta K+1 nava spatiala are doua optiuni: viteza normala sau superviteza. Folosind viteza normala, timpul calatoriei de la planeta K la planeta K+1 este Nk unitati de timp. Folosind superviteza, timpul calatoriei dintre planetele K si K+1 este Hk unitati de timp. Pilotul navei spatiale este interesat sa consume cat mai putin combustibil in calatoria sa. El stie ca formula pentru consumul de combustibil este: NTOTAL + HTOTAL4, unde NTOTAL este totalul unitatilor de timp in care a folosit viteza normala, iar HTOTAL este totalul unitatilor de timp in care a folosit superviteza. De exemplu, sa presupunem ca sunt 5 planete. De la planeta 1 la planeta 2 nava spatiala calatoreste 60 unitati de timp folosind viteza normala. De la planeta 2 la planeta 3 nava spatiala calatoreste 3 unitati de timp folosind superviteza.
De la planeta 3 la planeta 4 nava spatiala calatoreste 40 de unitati de timp folosind viteza normala. De la planeta 4 la planeta 5 nava spatiala calatoreste 7 unitati de timp folosind superviteza. NTOTAL = 60 + 40 = 100 si HTOTAL = 3 + 7 = 10. Consumul de combustibil este 100 + 104 = 10100.

Cerinta

Determinati Consumul minim de combustibil necesar calatoriei de la planeta 1 la planeta N.

Date de Intrare

Prima linie a fisierului de intrare calatorie.in contine numarul de teste T. Urmatoarele linii descriu cele T teste. Prima linie a fiecarui test contine numarul de planete N. Urmatoarele N-1 linii contin 2 numere intregi, NK si HK, pentru K = 1,2,..,N-1.

Date de Iesire

Pentru fiecare test afisati in fisierul calatorie.out o singura linie care sa respecte urmatorul format: Consumul minim = XXX., unde XXX trebuie inlocuit cu numarul gasit de programul vostru.

Restrictii

  • 1 ≤ N ≤ 50
  • 1 ≤ T ≤ 155
  • 1 ≤ Nk ≤ 108
  • 1 ≤ Hk ≤ 10

Exemplu

calatorie.incalatorie.out
2
4
1000 3
5000 2
8000 4
6
10000 1
3547 2
36782 7
2178 4
67428 9
Consumul minim = 2296.
Consumul minim = 52507.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content