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)
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) |