#2248. Bakterie [A]

Bakterie [A]

Bakterie [A]

题目描述

Zadanie: BAK Bakterie [A] 16.12.2022 Potyczki Algorytmiczne 2022, runda piąta. Limity: 512 MB, 10 s. Profesor Albert Bajtsztajn aktualnie bada nowo odkryty szczep bakterii, którym nadał roboczą nazwę Algorithmic Proeliis. Do jego następnego eksperymentu przygotował duży, prostokątny stół, który podzielił na n · m pól ułożonych w n rzędach po m pól w każdym. Następnie, profesor dla każdego pola wybrał jedną z trzech opcji: albo na pewno umieści w nim szalkę Pe- triego, albo zdecydowanie tego nie zrobi, albo rzuci uczciwą monetą aby o tym zdecydować. Po rozmieszczeniu szalek, jedyne co pozostanie do zrobienia, aby rozpocząć eksperyment, to wybrać dodatnią liczbę całkowitą k i w każdej szalce umieścić dokładnie k bakterii. Algorithmic Proeliis charakteryzują się bardzo wrogim nastawieniem do innych kolonii, zatem przebieg eksperymentu będzie następujący: dopóki istnieje para sąsiadujących, niepustych szalek, będzie losowana jedna taka para (z równym rozkładem prawdopodobieństwa), po czym w obu szalkach zginie po jednej bakterii. Przyjmujemy, że dwie szalki sąsiadują ze sobą wtedy i tylko wtedy, gdy pola na których stoją mają wspólny bok. Biorąc pod uwagę losowość przy rzutach monetą dla decyzji o umieszczeniu szalki w niektórych polach oraz losowość przy wyborze par sąsiadujących szalek w których będą ginęły bakterie, niech f(k) oznacza oczekiwaną liczbę bakterii, które przetrwają cały eksperyment. Eksperyment oczywiście kończy się, gdy nie ma już żadnej pary sąsiadujących szalek zawierających po co najmniej jednej bakterii. Ciężko byłoby umieszczać w szalkach po kilka bakterii. Znacznie łatwiej jest umieszczać ich dużo na raz. Z tego względu profesor zamyślił się, po czym napisał na tablicy następujące wyrażenie: f(k) lim k k→∞ Twoim zadaniem, jako jego asystenta, jest policzyć wartość powyższej granicy. Można udowodnić, że wartość ta jest zawsze liczbą wymierną, przedstaw ją zatem w postaci ułamka nieskracalnego. Wejście W pierwszym wierszu wierszu standardowego wejścia znajdują się dwie liczby całkowite n i m (1 ≤n, m ≤200), oznaczających wymiary stołu. W kolejnych n wierszach znajduje się opis stołu przygotowanego przez profesora. i-ty z tych wierszy zawiera m znaków, gdzie j-ty z nich to ai,j. Jeśli ai,j to ‘.’, to pole w i-tym rzędzie i j-tej kolumnie na pewno pozostanie puste. Jeśli ai,j to ‘O’ (duże ‘o’), to w polu w i-tym rzędzie i j-tej kolumnie na pewno zostanie umieszczona szalka Petriego. Jeśli ai,j to ‘?’, to profesor rzuci monetą aby zdecydować czy w polu w i-tym rzędzie i j-tej kolumnie zostanie umieszczona szalka. Wyjście W jedynym wierszu wyjścia powinna znaleźć się odpowiedź na pytanie profesora, wypisana w postaci ‘a/b’, gdzie b ≥1 oraz NWD(a, b) = 1. Przykład Dla danych wejściowych: poprawnym wynikiem jest: 4 5 5/2 O...O ?OO.? .OOO. ?..O. 1/2 Bakterie [A] Podzadania • W niektórych grupach testów opis stołu nie zawiera znaków ‘?’. • W niektórych grupach testów opis stołu zawiera co najwyżej 5 znaków ‘?’. • W niektórych grupach testów zachodzi warunek n ≤1. • W niektórych grupach testów zachodzi warunek n ≤2. • W niektórych grupach testów zachodzi warunek n, m ≤25. • W niektórych grupach testów jeśli (i · j) jest podzielne przez 5, to ai,j to ‘.’. Dla każdego wyżej wymienionego przypadku istnieje co najmniej jedna grupa która go spełnia. Grupy te dla różnych warunków mogą być rozłączne lub nie. 2/2 Bakterie [A]

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 5
O...O
?OO.?
.OOO.
?..O.
5/2