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 pracuje jako programista w latach 60. XX wieku.
Jest to praca mozolna, gdyż programy wprowadza do komputera nie za pomocą klawiatury, lecz przy użyciu kart perforowanych.
Karta rozmiaru składa się z
jednakowych, prostokątnych pól ułożonych w
kolumn po
wierszy.
Każde z pól może zostać przedziurkowane.
Układ dziurek w karcie koduje treść programu.
Na poniższym rysunku przedstawiono przykładową kartę rozmiaru
.
Dziurki w polach zostały zaznaczone czarnymi prostokątami.
Bajtazar ma już w głowie program i wie, które pola powinien przedziurkować.
Chciałby jednak przygotować kartę możliwie efektywnie.
W tym celu postanowił, że wykona prostokątną matrycę, która przyłożona do karty przedziurkuje wszystkie pola
w wybranym przez Bajtazara fragmencie rozmiaru (tj. pola należące do przecięcia
kolejnych wierszy z
kolejnymi kolumnami).
Rozmiar tej matrycy powinien być dobrany tak, by przy jej użyciu dało się wykonać kartę perforowaną
posiadającą dziurki dokładnie w tych miejscach, w których zaplanował je Bajtazar.
Jednocześnie, matryca powinna być jak największa.
Ponieważ pola na karcie nie są kwadratowe, matrycy nie wolno obracać (np. by otrzymać matrycę rozmiaru
).
Programowanie komputerów zajmuje dziś znacznie mniej czasu niż kiedyś, dlatego Bajtazar poprosił Cię o napisanie programu, który wyznaczy wymiary największej matrycy, za pomocą której można zapisać jego program na karcie.
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite oraz
(
).
Oznaczają one, odpowiednio, liczbę wierszy oraz kolumn na karcie perforowanej.
Kolejne
wierszy zawiera opis programu Bajtazara.
Każdy z tych wierszy składa się z
znaków "_" lub "X".
Znak "X" oznacza pole karty, które powinno zostać przedziurkowane, zaś "_" - pole, którego nie należy dziurawić.
Możesz założyć, że opis karty zawiera przynajmniej jeden znak "X".
Twój program powinien wypisać dwie liczby całkowite i
opisujące wymiary matrycy, która
może posłużyć do wykonania karty opisanej w wejściu.
Iloczyn tych dwóch liczb powinien być jak największy.
Jeśli istnieje wiele poprawnych odpowiedzi, Twój program powinien wypisać tę o jak najmniejszej wartości
.
Dla danych wejściowych:
4 5 _XXX_ XXXX_ XXXXX _XXXX
poprawną odpowiedzią jest:
2 3
Autor zadania: Jakub Łącki.