In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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
:
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.
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.
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 0poprawnym wynikiem jest:
3
natomiast dla danych wejściowych:
3 3 1 1 1 1 1 0 0 1 0poprawnym wynikiem jest:
2
Autor zadania: Tomasz Idziaszek