Feladat: I/S.26 Korcsoport: - Nehézségi fok: -
Füzet: 2018/április, 231 - 232. oldal  PDF  |  MathML 
Témakör(ök): Nehezebb feladat, Programozás, algoritmusok

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Informatikusok a 21-es játék egy módosított, digitalizált változatával játszanak. Nem kártyával, hanem számítógép segítségével. A gép a játék megkezdésekor mindegyik játékosnak előállít egy 64 hosszú, 1 és 9 közötti egészeket tartalmazó sorozatot ‐ ezek lesznek egy-egy játékos ,,felhúzható lapjai''. A játék körökből áll, melyek során minden játékos ,,húzhat'' a neki sorsolt lapok közül, vagy ,,dobhat'' a kezében található lapok közül. Fontos szabály, hogy húzni vagy dobni csak pontosan 1, 2, 4 vagy 8 számú lapot szabad. A játékos a dobáshoz bármely kártyalapokat kiválaszthatja a kezéből, de húzni csak a számsorozat sorrendben következő, megfelelő darabszámú lapját szabad. A játékosok kezdetben egy lappal sem rendelkeznek. Az a játékos győz, akinek elsőként lesz a kezében az adott körben történt húzása vagy dobása után 21 a számok összege. A játék során a kézben tartott lapok összege meghaladhatja a 21-et, ez nem jelent kiesést.
Természetesen minden játékos vihetett magával egy programozható eszközt, és annak segítségével is játszhatott. Készítsünk olyan programot, amely a 64 egész ismeretében meghatározza az egyes körökben a húzások és dobások stratégiáját úgy, hogy a lehető legkevesebb kört kelljen a játékosnak játszania a 21 eléréséhez.
A megoldást adó program a standard bemenetről olvassa be a 64 egész számot, majd írja ki a standard kimenet első sorába a 21 eléréséhez szükséges legkevesebb körök számát, illetve a következő sorokban a játékos kezében lévő kártyákat növekvő sorrendben. Amennyiben a 21 nem elérhető a 64-es sorozatból szabály szerinti húzásokkal és dobásokkal, akkor a kimenet csak egy 0 legyen. Amennyiben azonos számú kör, de különböző húzások és dobások esetén is elérhető a 21, akkor bármelyik megoldás elfogadható.
Példa:

 
Bemenet (nem teljes, de nemKimenet (a /  jel sortörést jelöl)   lényeges a további része)2 3 7 4 9 8 4 5 3 3   ...3 / 2 / 2 3 4 7 9 / 2 3 7 9   
 

Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra a programra, amely nem minden bemeneti értékek esetén ad helyes eredményt 1 másodpercen belül.
Beküldendő egy is26.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja.