Cieśla
Limit pamięci: 128 MB
Bajtazar chętnie zagrałby w warcaby, ale jego szachownica gdzieś się zawieruszyła.
Udało mu się tylko znaleźć drewnianą deskę rozmiaru podzieloną na
jednakowych kwadratowych pól. Każde pole jest pomalowane na biało lub czarno, ale
rozkład kolorów na desce niekoniecznie odpowiada planszy do warcabów.
Bajtazar postanowił zatem wykorzystać swoje ciesielskie umiejętności i za pomocą piły wyciąć
szachownicę, czyli kwadrat składający się z pewnej
liczby pól, w którym każde dwa pola o wspólnym boku mają różne kolory.
Nie jest jasne, czy Bajtazarowi uda się znaleźć na desce kwadrat o odpowiedniej wielkości.
Dlatego stwierdził on, że wytnie z deski dwa trójkątne kawałki i sklei je
razem w taki sposób, by powstała szachownica.
(Kawałki muszą być rozłączne, ale można je po wycięciu w dowolny sposób obracać.)
Pomóż Bajtazarowi i oblicz, jaki jest największy rozmiar szachownicy, którą może
on w ten sposób wyprodukować.
Poniższy obrazek przedstawia deskę rozmiaru i dwa trójkąty, które można
skleić razem w szachownicę rozmiaru :
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite
i (),
które oznaczają rozmiar deski.
Kolejne wierszy zawiera po liczb całkowitych:
-ta liczba z -tego wiersza (, )
oznacza kolor pola leżącego na przecięciu -tej kolumny i -tego
wiersza deski.
Liczba 0 oznacza białe pole, a liczba 1 - pole czarne.
Wyjście
W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą,
oznaczającą największy rozmiar szachownicy, którą można uzyskać przez
wycięcie z deski dwóch trójkątnych kawałków i sklejenie ich.
Przykład
Dla danych wejściowych:
4 5
1 1 0 1 1
0 1 0 1 0
1 0 1 0 0
0 0 1 1 0
poprawnym wynikiem jest:
3
natomiast dla danych wejściowych:
3 3
1 1 1
1 1 0
0 1 0
poprawnym wynikiem jest:
2
Autor zadania: Tomasz Idziaszek