1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <iomanip>

using namespace std;

bool can_schedule_sleep(int n, int L, const vector<string>& schedules, double T) {
    vector<int> coverage(L, 0);
    
    for (int i = 0; i < n; ++i) {
        vector<int> free_intervals;
        for (int j = 0; j < L; ++j) {
            if (schedules[i][j] == '.') {
                free_intervals.push_back(j);
            }
        }
        
        // Próbujemy zaplanować sen dla tej osoby
        for (int start : free_intervals) {
            int end = start + T;
            if (end <= L) {
                for (int k = start; k < end; ++k) {
                    coverage[k] += 1;
                }
            }
        }
    }
    
    // Sprawdzamy, czy w każdym momencie ktoś czuwa
    for (int i = 0; i < L; ++i) {
        if (coverage[i] == 0) {
            return false;
        }
    }
    return true;
}

pair<int, int> max_sleep_time(int n, int L, const vector<string>& schedules) {
    double low = 0, high = L;
    double best_T = -1;
    
    while (low <= high) {
        double mid = (low + high) / 2;
        if (can_schedule_sleep(n, L, schedules, mid)) {
            best_T = mid;
            low = mid + 1e-9;  // Używamy małej wartości, aby uniknąć problemów z precyzją
        } else {
            high = mid - 1e-9;
        }
    }
    
    if (best_T == -1) {
        return {-1, 1};  // Zwracamy -1
    }
    
    // Zwracamy wynik w postaci nieskracalnego ułamka
    int numerator = static_cast<int>(best_T * 1000000); // Używamy dużej liczby, aby uzyskać dokładność
    int denominator = 1000000;
    
    // Uproszczenie ułamka
    int gcd = std::gcd(numerator, denominator);
    numerator /= gcd;
    denominator /= gcd;
    
    return {numerator, denominator};
}

int main() {
    int n, L;
    cin >> n >> L;
    vector<string> schedules(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> schedules[i];
    }
    
    auto result = max_sleep_time(n, L, schedules);
    
    if (result.first == -1) {
        cout << -1 << endl;
    } else {
        cout << result.first << "/" << result.second << endl;
    }
    
    return 0;
}