Mastermind II
Limit pamięci: 32 MB
Będziemy rozważali ciągi, które spełniają następujące warunki:
- długość ciągu wynosi ,
- elementami ciągu są cyfry z zakresu 1-9,
- wyrazy ciągu się nie powtarzają.
Pojedynczy ciąg będziemy nazywali
układem.
Mając dane dwa układy, ich zgodność oceniamy podając dwie liczby.
Pierwsza z nich (kolumna A w przykładzie)
to suma cyfr, które występują w obu układach
i znajdują się na tej samej pozycji w obu ciągach,
natomiast druga (kolumna B), to suma cyfr, które
występują w obu układach,
ale znajdują się na różnych pozycjach.
Mamy dane układów i podane oceny ich zgodności
z pewnym nieznanym układem.
Należy podać nieznany układ.
Poniżej przedstawiono przykładowe dane i wynik dla .
Zadanie
Napisz program, który:
- wczyta opis układów i oceny ich zgodności,
- znajdzie układ spełniający warunki zadania,
- wypisze wynik.
Wejście
Twój program powinien czytać opis ze standardowego wejścia.
W pierwszym wierszu zapisana jest jedna liczba
całkowita , .
W kolejnych wierszach opisane są podane układy cyfr oraz
ocena ich zgodności z pewnym nieznanym układem, po jednym w wierszu.
W każdym z tych wierszy zapisanych jest po nieujemnych liczb
całkowitych pooddzielanych pojedynczymi odstępami.
Pierwsza i druga liczba są oceną zgodności danego układu
z nieznanym układem.
Ostatnie liczb, to różne cyfry z zakresu 1-9 tworzące dany układ.
Wyjście
Twój program powinien wypisać na standardowe wyjście
różnych cyfr z zakresu 1-9 tworzących poszukiwany układ,
oddzielonych pojedynczymi odstępami.
Możesz założyć, że dla danych testowych istnieje
co najmniej jedno rozwiązanie.
Jeżeli dla danych wejściowych istnieje wiele pasujących układów,
Twój program powinien wypisać tylko jeden z nich.
Przykład
Dla danych wejściowych:
3
4 0 4 9 7
0 10 6 7 4
0 5 9 4 1
poprawną odpowiedzią jest:
4 1 6
Autor zadania: Zbigniew Czech.