Problem description
Jaś spał pod kamieniem przez ostatnie dziesięciolecia i dopiero dzisiaj odkrył jeden z najbardziej popularnych automatów komórkowych, nazywanych po polsku Gra w życie.
Idąc za Wikipedią, gra toczy się na nieskończonej planszy podzielonej na kwadratowe komórki. Każda komórka ma ośmiu sąsiadów (komórki przylegające do niej bokami lub rogami). Komórki mogą być żywe lub martwe. Stan komórek z momentu T jest używany do obliczenia stanu komórek w momencie T + 1. Martwa komórka, która ma dokładnie trzech żywych sąsiadów, staje się żywa w następnej jednostce czasu. Żywa komórka z dwoma lub trzema żywymi sąsiadami pozostaje w następnej jednostce czasu żywa. Przy innej liczbie sąsiadów żywa komórka umiera (a martwa pozostaje martwa).
Okazuje się, że tak proste reguły pozwalają na uzyskiwanie bardzo ciekawych struktur (polecamy po turnieju przejrzeć podlinkowany artykuł z Wikipedii).
Jasio nie ma nieskończonej pamięci w komputerze, żeby symulować grę w życie. Dlatego symuluje ją na skończonej planszy o wymiarach 15 × 15. Zastanawia się czy symulacja ewolucji z jego początkowego układu ma sens na tak małej planszy: być może w którymś momencie struktura wyewoluuje poza zakres planszy. A być może nie? Jaś chciałby to wiedzieć. Pomożesz mu?
Wejście
Wejście składa się z piętnastu wierszy po piętnaście znaków. Każdy
znak to . lub O (duża litera o),
oznaczające odpowiednio martwą lub żywą komórkę.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna T, określającą pierwszy moment, w którym struktura przekroczy ramy początkowej planszy.
Jeżeli T > 100 lub
struktura nigdy nie przekroczy ramy początkowej planszy, to zamiast tego
należy wypisać tylko jedno słowo NIE.
Zadanie bonusowe
Po turnieju spróbuj wygenerować test, dla którego odpowiedź T jest skończona, ale większa niż 100.
Przykład
| Wejście | Wyjście | |
|
|