Társasjáték
A feladat szövege
A nagy multú Központi Társasjátékgyárnál az utóbbi időben rosszul mennek a dolgok. A piac átrendeződött a számítógépes játékok javára, a vezetőség pedig hibás döntések sorozatát hozta. A 2005-ös karácsony a cég utolsó esélye a csőd ellen, de csak akkor, ha valami igazán nagy újdonsággal rukkolnak elő.
A kreatív csapat kitett magáért, és most a Szoftveres Játékelemzési Divízión a sor, hogy kiválassza a legjobb játékokat. A Te feladatod a "Csúszdák és Létrák" típusú, titokban kifejlesztett játékcsalád elemzése.
A játék
Ezek a játékok mindig N (1<=N<=1000) mezőből állnak, és több játékos játsza őket. Mindenki az 1. (start) mezőből indul. A játékosok felváltva dobnak a dobókockával, és mindenki annyi mezőt lép előre, ahányat dobott. Egy mezőn csak egy játékos állhat, a bábuk leüthetik egymást. A leütött bábuk az első mezőre kerülnek.
- Létra: egy ilyen mezőről egy létra vezet egy magasabb sorszámú mezőre. Ha idelép a játékos, akkor még rögtön abban a körben felmászik a létra tetején lévő mezőre.
- Csúszda: egy ilyen mezőről egy csúszda vezet egy alacsonyabb sorszámú mezőre. Ha idelép a játékos, akkor még rögtön abban a körben lecsúszik a csúszda alján lévő mezőre.
- Egyszer kimaradsz: Ha rálép a játékos, akkor kimarad a következő körből, aztán játszhat tovább.
Csúszda alján, illetve létra tetején sosincs újabb csúszda vagy létra.
Az nyer, aki elsőként lép az N. mezőre. Annak is a erre a mezőre kell lépnie, aki a dobása alapján túllépne rajta.
Feladat
Készíts programot, ami beolvassa egy ilyen játék leírását, és elvégez egy játékszimulációt, véletlen kockadobásokkal. A kérdés az, hogy az első játékos hányadik körben fog célba érni. Megjegyzés: ha a körök száma túllépi a 30,000-et, akkor nem kell a programnak helyes eredményt adnia.
Bemenet
Az első sora N, M egész számokat tartalmazza, ahol 6<=N<=1000 a mezők száma, 1<=M<=10 pedig a játékosok száma. A következő N sor a játékpálya mezőit írja le, és két számot tartalmaznak. 1<=A<=N, 0<=B<=7. A az ugrási mező: azt adja meg, hogy ha a bábu rálép az adott mezőre, akkor hova kerül valójában. Ha A az adott mező sorszáma, akkor nem történik semmi, ha kisebb a sorszámnál, akkor csúszda mezőről van szó, ha pedig nagyobb, akkor létra mezőről. Ha B nem 0, akkor a játékos a mezőre lépés után kimarad egy körből, egyébként ha 0, akkor nem okoz semmit.
Kimenet
A szimulált játék után a játékos beérésehez szükséges körök száma. Minden megkezdett kör számít.
Megjegyzések
A feladat megoldása közben felmerült néhány a specifikációban nem szereplő kérdés. Ezekre a szakkörön kerestünk válaszokat:
- Ha az első mezőn nemnulla szám áll, akkor az első körben nem kell kimaradni, de ha leütés vagy csúszda miatt kerül oda a bábu, akkor ki kell maradni.
- Egy mező csúszda/létra tulajdonsága erősebb, mint az "egyszer kimaradsz" tulajdonság. Tehát ha a játékos egy olyan mezőre lép, ami pl. csúszda, és "egyszer kimaradsz" egyszerre, akkor lecsúszik, de nem marad ki. Természetesen, ha a csúszda végén is "egyszer kimaradsz" mező van, akkor ott már ki fog maradni a játékos.
- Az egyszer éppen kimaradó játékost leütve a játékosnak a leütés után már nem kell kimaradnia.
További feladatok
A cég külső szakértők segítségét is igénybe vette, akik a következő javaslatokkal álltak elő:
- Legyenek csapda mezők: Ha a játékos egy ilyen mezőre lép, akkor onnan csak adott dobásra léphet tovább. (Tehát pl. sok játékban első mezőn 6-ot kell dobni a kezdéshez.) Az ilyen dobást sosem szabad lelépni, hanem egy újat kell dobni. B értéke fogja kijelölni az ilyen mezőket, ha 1 és 6 közé esik. B=7 továbbra is egyszer kimaradsz típusú marad.
- A célba csak pontosan lehessen belépni. Ha valaki túl sokat dob, akkor a felesleges lépéseket visszafelé kell megtennie.
- Végezzen el a program 1000 játékszimulációt, és írja ki nyertes köreinek a mért minimális, maximális és átlagos számát.