NézetNyomtat

Lift (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Mohó
Címkék > Hiányzó algoritmus

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 uticé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

Készíts programot (LIFT.PAS vagy LIFT.C), amely 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\leq N\leq 500)$ száma, $K$ $(1\leq K\leq 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

lift.belift.ki
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