Fişierul intrare/ieşire:raliu.in, raliu.outSursăAlgoritmiada 2011, Runda 2
AutorAndrei Ciupan, Andrei ParvuAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test2.9 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Raliu

După ce s-a plimbat cu maşina prin Bucureşti, Alex a decis că trebuie să participe la un campionat de raliu. Singura sa problemă este că nu are foarte multă benzină, astfel că trebuie să se folosească de benzinăriile puse la dispoziţie de organizatori. Traseul are o formă circulară şi are N benzinării dispuse de-a lungul acestuia. Pentru fiecare din cele N benzinării se ştie numărul de litri cu care poţi alimenta, dar şi numărul de kilometri până la următoarea benzinărie.
Ajutaţi-l pe Alex să aleagă o benzinărie de la care să pornească astfel încât să poată face un tur complet al traseului, fără a ramane fără benzină.

Date de intrare

Fişierul de intrare raliu.in conţine pe prima linie T, numărul de teste.
Fiecare test are următorul format: pe prima linie N, numărul de benzinării, pe următoarea linie N numere întregi, al i-lea număr reprezentând numărul de litri de benzină disponibili la benzinăria i, iar pe cea de-a treia linie N numere întregi, al i-lea număr reprezentând distanţa de la benzinăria i la benzinăria i+1.

Date de ieşire

În fişierul de ieşire raliu.out se vor afişa răspunsurile pentru cele T teste.
Răspunsul pentru un test poate fi "DA" (fără ghilimele) urmat de o linie pe care se află indicele benzinăriei de unde poate pleca Alex, sau "NU" (fără ghilimele) în cazul în care nu se poate efectua un tur complet al traselui.

Restricţii si precizari

  • 1T ≤ 5
  • 2N1 000 000
  • 0 ≤ număr de litri, număr de kilometri ≤ 2147483640
  • Iniţial rezervorul de benzină al masinii lui Alex este gol şi are capacitate nelimitată
  • Traseu este circular, deci după benzinăria N urmeaza benzinăria 1
  • Un tur complet al traseului reprezintă plecarea de la o benzinărie i, parcurgerea tuturor benzinăriilor si întoarcerea la benzinăria i
  • Maşina lui Alex consumă 1 litru de benzină pentru fiecare kilometru parcurs (nu este o maşină foarte bună)
  • În caz că există mai multe soluţii se va afişa cea cu indicele minim
  • Atentie! Alex vă recomandă să folosiţi tipuri de date pe 64 de biţi.

Exemplu

raliu.inraliu.out
2
5
2 6 1 7 3
3 5 3 3 4
3
1 3 4
7 2 2
DA
4
NU
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content