Vasút
(Megoldás)
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2010 > Döntő > 11-13. évfolyam
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2010 > Döntő > 11-13. évfolyam
Vasút
Duplaverem város vasútállomásán sok gondot okoz a vasúti kocsik rendezése. Az állomásról továbbítandó szerelvényeket úgy kell kialakítani, hogy amikor az megérkezik a célállomásra, a szerelvény végéről mindig lekapcsolható legyen az oda továbbított kocsisor. Minden továbbítandó szerelvény négy állomást érint, ezért a rendezés előtt minden kocsit megjelölnek az 1, 2, 3 vagy 4 számokkal. A szerelvény kocsijait át kell rendezni úgy, hogy a szerelvény elején legyenek az 1-essel, aztán a 2-essel, majd a 3-assal, végül a 4-essel megjelöltek. Kezdetben a kocsik az ábrán látható B pályaszakaszon vannak.
A vasúti váltók működése csak a következő műveleteket teszi lehetővé. Az átrendezendő kocsisorból balról az első kocsit át lehet mozgatni vagy az A szakaszba a már ott lévő kocsik mögé, vagy a C vagy D szakaszba a már ott lévő kocsik elé. Továbbá, a C vagy D szakaszon lévő első kocsit át lehet mozgatni az A szakaszon kialakítandó rendezett kocsisor végére.
Feladat
Készíts programot (VASUT.PAS, VASUT.C, …), amely megállapítja, hogy a beérkező kocsisor rendezhető-e!
Bemenet
A VASUT.BE szöveges állomány első sorában a rendezésre váró szerelvények N száma van ($1\leq N \leq 20$). A következő N sor mindegyike egy legfeljebb 1000 kocsit tartalmazó rendezendő szerelvényt ír le, minden sort a 0 szám zárja (ami nem része a bemenetnek). Az utolsó 0 kivételével minden szám értéke 1,2,3 vagy 4.
Kimenet
A VASUT.KI szöveges állományba pontosan N sort kell írni! Az i-edik sorba az IGEN szót kell írni, ha a bemenet i+1-edik sorában szereplő kocsisor rendezhető, egyébként pedig a NEM szót!
Példa
| VASUT.BE | VASUT.KI |
| 2 1 2 3 2 4 0 2 3 1 4 2 1 0 | IGEN NEM |