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.
Fifolandia ponownie jest w stanie wojny z Wielką Barańską Gogolską Dżamahirijją Ludową. Ostała się już tylko ostatnia jednostka nieprzyjaciela, która ukryła się gdzieś w lesie. Kapral Fifuś jest odpowiedzialny za zorganizowanie obławy na oddział nieprzyjaciela.
W związku z tym Fifuś szybko znalazł mapę lasu o rozmiarze , na której dla każdego jednostkowego kwadratu oznaczone jest, czy znajdują się na nim bagna, czy też nie. Na mapie pola, na których jest bagno, są oznaczone jako , natomiast pozostałe pole, na których nie ma bagien, są oznaczone jako . Oczywiście oddziały Fifusia nie mogą stacjonować na obszarze, na którym znajduje się bagno. Ponadto w wojskowym prawie Fifolandii jest dokładnie określone, jak powinna wyglądać obława, a Fifuś musi przestrzegać tych zasad.
Zgodnie z wojskowym prawem Fifolandzkim otaczając przeciwnika, należy tak rozmieścić wojska, aby tworzyły obwód kwadratu o boku co najmniej . Podobno takie rozmieszczenie gwarantuje, że wojskom przeciwnika nie uda się uciec. Na nieszczęście Fifuś nie ma najmniejszego pojęcia, gdzie mogą znajdować się wojska przeciwnika. Dlatego zanim Fifuś zdecyduje, w którym miejscu rozpocząć obławę, zastanawia się, na ile sposobów można to zrobić.
Zakładamy, że wojska Fifolandii nie będą miały problemów z dotarciem w dowolne miejsce, które nie jest bagnem - mogą do tego użyć np. helikopterów.
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą długość boku mapy. Następnie na wejściu pojawi się wierszy. W -tym wystąpi ciąg cyfr - zera lub jedynki. Jeżeli , oznacza to, że na danym polu jest bagno, natomiast oznacza, że na danym polu nie ma bagna.
Możesz założyć, że w testach wartych około zachodzi dodatkowy warunek .
Pierwszy wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą liczbie sposobów, na które Fifuś może rozmieścić wojska.
Dla danych wejściowych:
6 111110 101010 011111 011101 101011 011111
poprawną odpowiedzią jest:
5
Wyjaśnienie do przykładu: Fifuś może rozmieścić wojsko na obwodzie kwadratów, których współrzędne lewego górnego rogu to:
Autor zadania: Łukasz Jocz.