Programozás‎ > ‎Feladatok‎ > ‎

Lift

Egy sokemeletes házban szokatlan módon üzemeltetik a liftet. A lift az első szintről indul és mindig felmegy a legfelső szintre, majd visszatér az első szintre. Menet közben megáll minden olyan szinten, amelyik úti célja valamelyik liftben tartózkodó utasnak. Hasonlóan, olyan szinten is megáll, ahonnan utazni szándékozik valaki az aktuális irányban, feltéve, hogy még befér a liftbe (figyelembe véve az adott szinten kiszállókat). 

Feladat

Írjunk programot, ami kiszámítja, hogy legkevesebb hány menet szükséges ahhoz, hogy minden várakozó embert elszállítson a lift.

Bemenet

A LIFT.BE bemeneti állomány első sorában két szám van, N és K. N az épület szintjeinek (2 <= N <= 500) száma, K (1 <= K <=20) pedig a lift kapacitása. A további N sor tartalmazza az egyes szinteken várakozó emberek adatait. Az állomány i-edik sorában azoknak a szinteknek a sorszáma van felsorolva, ahová az (i-1)-edik szintről utazni akarnak. Minden sorban legfeljebb 500 szám lehet, a felsorolást egy 0 szám zárja.

Kimenet

A LIFT.KI állomány egyetlen sort tartalmazzon, a legkevesebb menetek számát, amely az emberek elszállításához szükséges!

Példa

Bemenet  Kimenet
6 2
2 3 2 0
1 3 0
1 2 0
2 5 0
3 6 2 0
1 2 3 0
3


Tesztadatok

Címkék

A feladat forrása: Nemes Tihamér OITV 2000, 2. forduló, 11-13. évfolyam
Algoritmusok: mohó algoritmus