Programozás‎ > ‎Feladatok‎ > ‎

Társasjáték

A nagy múltú 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átssza ő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<=N0<=B<=7A 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éséhez 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.

Tesztadatok

BemenetAz alapváltozat kimenetei 10 futtatása: min/max/átlagA bővített változat kiemenete: min/max/átlag
3/15/6.93/147/ 25.64
5/39/16.95/146/ 34.66
13/227/143.38/1227/116.63
29/627/315.720/4818/657.35

Címkék

A feladat forrása: saját feladat
Algoritmusok: ???

megoldás