Úloha: Pomocník pro Mastermind--
Hra Mastermind-- vychází ze hry Mastermind (u nás známé také pod označním "hra logik").
Pravidla hry
Mastermind-- hrají dva hráči, z nichž jeden vytvoří tajnou variaci k kolíčků vybraných z pytlíku s n kolíčky a druhý se ji snaží uhodnout.
Pytlík obsahuje kolíčky s čísly. Pokud se v pytlíku vyskytují dva kolíčky se stejným číslem, pak jsou vzájemně nerozlišitelné. Obsah pytlíku je před začátkem hry znám oběma hráčům, ale ihned po vytvoření tajné variace prvním hráčem je pytlík dobře skryt.
Hádání tajné variace probíhá v krocích. V každém kroku vytvoří druhý hráč vlastní variaci délky k. Říkejme jí pokus. Po každém pokusu se hádající hráč dozví od prvního hráče Hammingovu vzdálenost svého pokusu od tajné variace.
Protože oba hráči znají obsah pytlíku před vytvořením tajné variace, nemůže druhý hráč vytvořit pokus, který by nešel z pytlíku před vytvořením tajné variace sestavit.
Hra končí pokud druhý hráč svým pokusem uhodne tajnou variaci nebo pokud druhý hráč vyčerpá přidělený počet pokusů.
Aby bylo možné určit nejlepšího hráče po co nejmenším počtu her, vymysleli autoři hry Mastermind-- následující ohodnocovací funkci pro přidělování bodů oběma hráčům.
- Pokud druhý hráč svým pokusem uhodne tajnou variaci, získá tolik bodů, kolik pokusů mu ještě zbývá z přiděleného počtu.
- Pokud druhý hráč vyčerpá přidělený počet pokusů, získá první hráč tolik bodů, kolik různých korektních k-kolíčkových variací by mělo stejné hodnocení ve všech pokusech druhého hráče jako měla tajná variace.
Úloha
Vašim úkolem je vytvořit program, který pomůže hráčům snadno určovat bodový zisk prvního hráče v případě, že druhý hráč vyčerpal přidělený počet pokusů.
Program dostane na vstupu popis obsahu pytlíku před začátkem hry a průběh hry Mastermind-- bez tajné variace (tedy posloupnost dvojic pokus a Hammingovu vzdálenost od tajné variace) a na výstupu vypíše, kolik různých korektních k-kolíčkových variací by mělo stejné hodnocení ve všech pokusech druhého hráče jako měla tajná variace.
Přepokládejte, že oba hráči hráli přesně podle pravidel a formát vstupu je vždy korektní.
Vstup
- Na prvním řádku bude číslo n udávající počet kolíčků v pytlíku.
- Na druhém řádku bude n čísel oddělených mezerou reprezentujících obsah pytlíku, kde jednotlivá čísla mohou být v rozsahu od 0 do 255.
- Na třetím řádku bude číslo k udávající počet kolíčků v hledané variaci.
- Na čtvrtém řádku bude číslo udávající počet pokusů druhého hráče.
- Na dalších řádcích budou jednotlivé pokusy druhého hráče. Každý řádek s pokusem bude obsahovat k+1 čísel oddělených mezerou, kde první až k-té číslo bude hádaná variace a k+1 číslo bude její Hammingova vzdálenost od tajné variace.
Výstup
Výstupem bude vždy jediný řádek s celým číslem udávajícím, kolik různých korektních k-kolíčkových variací by mělo stejné hodnocení ve všech pokusech druhého hráče jako měla tajná variace.
Autoři hry Mastermind-- mají docela dobrý důvod se domnívat, že neexistuje polynomiální algoritmus, řešící zadanou úlohu vzhledem ke k. Na druhou stranu, vhodné využití informací o obsahu pytlíku a provedených pokusech může hrát rozhodující roli pro dostatečně rychlé řešení úlohy.
Příklad 1:
Vstup:
14 2 2 2 2 2 1 1 1 1 1 3 3 3 3 2 1 1 2 1
Výstup:
4
Pro informaci ještě přidáváme možné variace splňující podmíky úlohy:
2 2 3 2 1 1 1 3
Příklad 2:
Vstup:
23 9 2 2 2 2 2 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 8 5 2 9 8 3 2 1 5 1 2 3 8 9 1
Výstup:
2
Pro informaci ještě přidáváme možné variace splňující podmíky úlohy:
1 2 1 8 9 1 2 2 8 9
Příklad 3:
Vstup:
13 9 0 3 4 2 7 7 5 8 1 5 5 1 5 6 9 0 3 4 2 3 7 0 7 9 4 5 3 9 4 5 8 3 3 4 1 0 9 4 5 1 5 4 5 3 1 2 5 3 1 4
Výstup:
1
Pro informaci ještě přidáváme skrytou variaci: 3 9 5 4 2.