Fişierul intrare/ieşire:popas.in, popas.outSursăOJI 2004 clasa a 8-a
AutorAutor NecunoscutAdăugată defrancuCristian Francu francu
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Popas (clasa a 8-a)

Dornic de o condiţie fizică perfectă, un viitor olimpic naţional la informatică îşi propune să escaladeze cea mai înaltă culme a unui un masiv muntos. Se echipează corespunzator, îşi cumpără un termos, îl umple cu apă, culege informaţiile despre traseele existente şi completează astfel fişierul de intrare popas.in. Pe parcursul fiecărui traseu există mai multe izvoare de la care drumeţul îşi poate umple termosul. Ştiind că pe munte este bine să mergi cu pas constant şi fără ruperi de ritm, îşi propune să atingă culmea facând cât mai puţine popasuri (pentru umplerea termosului).

Cerinţă

Dintre toate traseele existente către culme determinaţi-l pe cel pentru care numărul total de popasuri este minim. Dacă sunt mai multe astfel de trasee, se va alege cel care este scris ultimul în fişierul de intrare.

Date de intrare

Fişierul de intrare popas.in conţine:

  • pe prima linie, k - numărul total de trasee către culme
  • pe fiecare dintre următoarele k linii descrierea câte unui traseu (pe fiecare linie numerele sunt separate prin câte un spaţiu), adică:
    • i - numărul asociat traseului (fiecare traseu este identificat în mod unic printr-un număr natural cuprins între 1 şi k)
    • r - numărul izvoarelor cu apă rece de pe traseu
    • d1, d2, ..., drr numere reprezentând distanţa de la punctul de plecare până la fiecare izvor
  • pe ultimele două linii:
    • t distanţa pentru care drumeţului îi este suficientă apa din termos
    • u distanţa pe care drumeţul o poate străbate fără apă

Date de ieşire

Fişierul de ieşire popas.out va conţine pe aceeasi linie, despărţite prin spaţiu, două numere: primul reprezintă numărul minim de popasuri necesare deplasarii şi al doilea numărul traseului ales. Dacă problema nu are soluţie fişierul de ieşire va conţine cifra 0.

Restricţii

  • 0 < k ≤ 100
  • 0 < r ≤ 20
  • 0 < di ≤ 360
  • 1 ≤ t ≤ 10
  • 1 ≤ u ≤ 5
  • În fişierul de intrare toate distanţele sunt exprimate în kilometri
  • Pentru fiecare traseu distanţa dintre ultimul izvor (cel mai îndepărtat de punctul de plecare) şi culme este de 1 kilometru.

Exemple

popas.inpopas.out
3
2 3 12 5 9
1 4 2 9 7 11
3 5 2 16 7 9 8
6
2
1 1
2
1 3 12 5 9
2 3 2 7 11
1
2
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici