Fișierul intrare/ieșire	popas.in, popas.out	Sursă	OJI 2004 clasa a 8-a
Autor	autor necunoscut	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

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
  • d₁, d₂, ..., d_r – r 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 < d_i ≤ 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