HONI 2. KOLO 2022 - 3. ZADATAK

Jedne čarobne večeri Patrik i Josip, vozeći se tramvajem, raspravljaju o smislu života. Prekinuo ih je svima poznat glas u tramvaju rekavši: Sljedeća je postaja: Jordanovac. Sada su Patrik i Josip, skrenuvši s teme, došli na temu tramvajskih stanica.

Patrik: Baš je kratka vožnja između Jordanovca i Maksimira.

Josip: Istina, ali je puno kraća između Mašićeve i Kvatrića.

Patrik: Stvarno? Meni se čini da nije.

Josip: Pitam se, koja je najkraća vožnja u Zagrebu?

Ovaj razgovor je pomno pratila Paula, velika ljubiteljica tramvaja. Misterija najkraće vožnje ju je toliko zaintrigirala da je odlučila ostati u tramvaju i prisluškivati naše junake.

Na svakoj stanici vožnje je ili Patrik prokomentirao Vozimo se već t minuta otkako smo ušli u tramvaj ili je Josip rekao Od stanice y do trenutne se vozimo već t minuta.

No prije nego što je Paula stigla čuti Patrikov i Josipov zaključak o najkraćoj vožnji, Patrik i Josip su izletjeli iz tramvaja. Srećom, Paula se sjeća tko je što rekao na kojoj stanici. Pomozite Pauli odrediti koliko je trajala najkraća vožnja između dviju stanice i koje su to stanice.

Ulazni podaci

U prvom retku nalazi se prirodan broj n (2 ≤ n ≤ 1 000), broj tramvajskih stanica.

U i-tom sljedećih n − 1 redaka nalazi se informacija o i + 1-toj stanici u jednom od dva oblika:

• Patrik ti – Prošlo je ti minuta u vožnji od prve stanice do stanice i + 1 (1 ≤ ti ≤ 109)

• Josip yi ti – Prošlo je ti minuta u vožnji od yi-te stanice do stanice i + 1 (yi < i + 1, 1 ≤ ti ≤ 109)

Ulazni podaci će biti takvi da se dvije stanice nikada neće nalaziti na istom mjestu.

Izlazni podaci

U jednom retku ispišite tri prirodna broja: t, x1, x2, gdje su x1 i x2 indeksi najbližih stanica, a t vrijeme potrebno da se od jedne dođe do druge.

Ako postoji više parova najbližih stanica, ispišite one s najmanjim brojevima oznaka

Primjeri test podataka

Ulaz

4
Patrik 3
Patrik 5
Josip 1 7

Izlaz

2 2 3

Objašnjenje

Budući da je od prve do druge stanice 3 minute vožnje, a od prve do treće 5 minuta, može se zaključiti da je od druge do treće 2 minute vožnje, što je i najmanje vrijeme između nekog para stanica.

Ulaz

2
Josip 1 5

Izlaz

5 1 2

Ulaz

5
Patrik 4
Josip 2 4
Josip 2 6
Josip 4 2

Izlaz

2 3 4

Objašnjenje

Od treće do četvrte stanice tramvaj se vozi 2 minute. Tramvaj se vozi 2 minute i između četvrte i pete stanice, no budući da su one su numerirane s većim brojevima to rješenje nije prihvaćeno.