Programozás‎ > ‎Feladatok‎ > ‎

Fadöntés

Egy fasorba N fát ültettek balról jobbra, egy vonalba. Mindegyik fának ismerjük a magasságát és a bal szélső fáról vett távolságát. Ha egy fát kivágunk, akkor az a jobboldali szomszédja felé dől, s amelyik szomszédjára rádől, az is kidől. 

Feladat

Készíts programot, amely megadja, hogy minimum hány fát kell kivágnunk ahhoz, hogy az összes fa kidőljön, s melyik fa kivágása okozza a legtöbb fa kidőlését! 

Bemenet

A standard bemenet első sorában a fák száma van (1 <= N <= 1000). A következő N sor mindegyike egy-egy fa leírását tartalmazza: a bal szélső fától vett távolságát (0 <= T <= 6000) és a fa magasságát (1 <= M <= 100). A fákat balról jobbra haladva adjuk meg. 

Kimenet

A standard kimenet első sorába a minimálisan kivágandó fák számát kell írni, a második sorába pedig annak a kivágandó fának a sorszámát, amely kivágása esetén a legtöbb fa fog kidőlni! 

Példa

Bemenet  Kimenet
5
0 6
3 1
5 2
8 1
15 10
3
1


Tesztadatok

További tesztadatok: mester.inf.elte.hu

Címkék

A feladat forrása: mester.inf.elte.hu, Haladó > Mohó algoritmusok > Fadöntés
Algoritmusok: mohó algoritmus

megoldás