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
90
91
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAX_L = 100000;
int n, L;
vector<string> schedule;

// Check if a given sleep time `T = p/q` is feasible
bool canScheduleSleep(ll p, ll q) {
    vector<vector<int>> free_intervals(n);

    // Convert `p/q` into an integer comparison
    ll sleepTime = p;  // We will scale everything by `q`

    // Find available intervals for each person
    for (int i = 0; i < n; i++) {
        vector<pair<ll, ll>> available;
        ll start = -1;
        for (ll j = 0; j < L; j++) {
            if (schedule[i][j] == '.') {
                if (start == -1) start = j;
            } else {
                if (start != -1) {
                    available.push_back({start, j});
                    start = -1;
                }
            }
        }
        if (start != -1) available.push_back({start, L});

        // Try placing sleep intervals of `sleepTime` within `available` segments
        ll needed = sleepTime;
        for (auto [l, r] : available) {
            ll len = (r - l) * q;  // Scale the interval
            ll take = min(needed, len);
            needed -= take;
            if (needed == 0) break;
        }
        if (needed > 0) return false;  // Not enough space for sleep
    }

    // Verify if at least one person is awake at all times
    vector<int> awake(L, 0);
    for (int i = 0; i < n; i++) {
        for (ll j = 0; j < L; j++) {
            if (schedule[i][j] == '.') awake[j]++;
        }
    }
    
    for (ll j = 0; j < L; j++) {
        if (awake[j] == 0) return false;  // No one is awake
    }

    return true;
}

// Compute GCD for fraction reduction
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Read input
    cin >> n >> L;
    schedule.resize(n);
    for (int i = 0; i < n; i++) cin >> schedule[i];

    // Binary search for maximum T = p/q
    ll left = 0, right = L, bestP = 0, bestQ = 1;
    while (left <= right) {
        ll mid = (left + right);
        if (canScheduleSleep(mid, 1)) {
            bestP = mid, bestQ = 1;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    // Reduce fraction
    ll g = gcd(bestP, bestQ);
    bestP /= g, bestQ /= g;

    // Print result
    if (bestP == 0) cout << "0/1\n";
    else cout << bestP << "/" << bestQ << "\n";

    return 0;
}