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.