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.
FeladatKé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!
BemenetA 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.
KimenetA 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
Tesztadatok
CímkékA feladat forrása: mester.inf.elte.hu, Haladó > Mohó algoritmusok > Fadöntés
Algoritmusok: mohó algoritmus
megoldás |
Programozás > Feladatok >