Nieatakujące się skoczki
Limit pamięci: 32 MB
Skoczek jest figurą, która atakuje pola na szachownicy zgodnie z poniższym rysunkiem
(skoczek umieszczony w polu atakuje pola oznaczone przez krzyżyk).
Dana jest szachownica o rozmiarach — mająca wiersze i kolumn, gdzie —
oraz zbiór pól na tej szachownicy.
Wiersze na szachownicy są ponumerowane od góry do dołu liczbami od do , a kolumny od lewej do prawej liczbami od do .
Na szachownicy wolno rozmieszczać skoczki tylko na polach nie należących do oraz tak,
aby żadne dwa nie atakowały się nawzajem.
Zakładamy, że w każdej kolumnie co najwyżej jedno pole należy do .
Zbiór można więc opisać w postaci ciągu: , gdzie .
Wartość oznacza, że żadne pole w -tej kolumnie nie należy do ,
zaś wartość jest numerem wiersza jedynego pola w tej kolumnie, które należy do .
Zadanie
Ułóż program, który:
- wczytuje ze standardowego wejścia liczbę kolumn na szachownicy oraz opis zbioru pól ,
- znajduje maksymalną liczbę skoczków , które można ustawić na szachownicy zgodnie z podanymi zasadami oraz liczbę wszystkich takich ustawień skoczków,
- zapisuje wyniki na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodatnia , .
Jest to liczba kolumn szachownicy.
W każdym z kolejnych wierszy jest zapisana jedna liczba ze zbioru .
Są to kolejne wyrazy ciągu będącego opisem zbioru pól .
Wyjście
Na standardowe wyjście należy zapisać dwie liczby całkowite i oddzielone odstępem.
Przykład
Dla danych wejściowych:
2
1
0
poprawną odpowiedzią jest:
4 2
Autor zadania: Wojciech Rytter.