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
from fractions import Fraction

def can_schedule_sleep(n, L, schedules, T):
    """Sprawdza, czy można zaplanować sen dla wszystkich opiekunów."""
    # Tworzymy listę dostępności
    available = [0] * L
    
    # Zbieramy dostępność opiekunów
    for j in range(n):
        for i in range(L):
            if schedules[j][i] == '.':
                available[i] += 1  # Zwiększamy licznik dostępnych opiekunów

    # Sprawdzamy, czy można zaplanować sen
    sleep_time = 0
    for i in range(L):
        if available[i] > 0:  # Jeśli przynajmniej jedna osoba jest wolna
            sleep_time += 1
        else:
            # Jeśli nie ma dostępnych opiekunów, resetujemy czas snu
            sleep_time = 0
        
        # Sprawdzamy, czy możemy zaplanować sen
        if sleep_time >= T:
            return True

    return False

def max_sleep_time(n, L, schedules):
    """Oblicza maksymalny czas snu dla opiekunów."""
    left, right = 0, L / n  # Zakres możliwego czasu snu
    best_T = -1

    while left <= right:
        mid = (left + right) / 2
        if can_schedule_sleep(n, L, schedules, mid):
            best_T = mid
            left = mid + 0.0001  # Szukamy większego T
        else:
            right = mid - 0.0001  # Szukamy mniejszego T

    if best_T == -1:
        return -1
    else:
        # Zwracamy wynik jako nieskracalny ułamek
        fraction_result = Fraction(best_T).limit_denominator()
        return f"{fraction_result.numerator}/{fraction_result.denominator}"

# Przykładowe dane wejściowe
n = 3  # Liczba opiekunów
L = 6  # Długość przedziału czasu
schedules = [
    "..X.XX",
    ".X..X.",
    "X..X.."
]

# Obliczenie maksymalnego czasu snu
result = max_sleep_time(n, L, schedules)
print(result)