W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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