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. Ifjú hercegünk egy hegyi ösvényen készül átkelni. Az ösvény mentén manók állnak lesben, akikkel semmiképp nem jó találkozni. Szerencsére a manók mindegyike olyan, hogy egy bizonyos színt nem lát. Hercegünk ezért varratott magának mindegyik színből egy-egy köpenyt, így ha a megfelelő manó előtt elhaladva azt viseli, akkor a manó nem veszi észre. A köpenyek mindegyike karra terítve is könnyen vihető, és emellett tetszőleges számú köpeny ‐ akár az összes ‐ egymásra fölvéve hordható. Ha a herceg már visel egy vagy több köpenyt, akkor a következőt azok fölé tudja venni. Vetkőzéskor mindig a legfelső köpenyt tudja levenni, tehát ha szüksége van egy most nem legfelül viselt köpenyre, akkor az összes fölötte lévőt le kell vennie. A herceg azt is megtudta, hogy milyen sorrendben következnek az egyes manók az ösvény mentén. Mivel nem szeretne sokszor öltözni, ezért szeretné tudni, hogy hogyan juthat túl a lehető legkevesebb számú öltözéssel az ösvényen. Az út megkezdése előtt nem viseli egyik köpenyt sem, és az ösvény után sem, tehát leveszi, ami még rajta van. Minden köpeny föl- vagy levétele egy öltözésnek számít. A feladatot megoldó program olvassa be a standard bemenetről a manók számát, illetve az általuk nem látott színek számát, majd a következő sorból számú pozitív egészet: az -edik szám az -edik manó által nem látott szín sorszáma. A program írja a standard kimenetre az ösvényen való áthaladáshoz szükséges legkevesebb öltözések számát. Példák:
Korlátok: , . É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 csak kisebb értékek esetén ad helyes eredményt 1 másodpercen belül. Beküldendő egy s119.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja. |