import sys from fractions import Fraction def main(): n, L = map(int, sys.stdin.readline().split()) schedules = [sys.stdin.readline().strip() for _ in range(n)] available = [] for s in schedules: intervals = [] start = None for i in range(L): if s[i] == '.': if start is None: start = i else: if start is not None: intervals.append((start, i)) start = None if start is not None: intervals.append((start, L)) available.append(intervals) all_available = [] for intervals in available: for a, b in intervals: all_available.extend([(a, True), (b, False)]) all_available.sort(key=lambda x: (x[0], not x[1])) coverage = 0 cnt = 0 last = 0 total_cover = True for pos, is_start in all_available: if cnt == 0 and is_start: if pos > last: total_cover = False break last = pos if is_start: cnt += 1 else: cnt -= 1 if cnt == 0: coverage += pos - last last = pos if last < L: total_cover = False if not total_cover: print(-1) return max_T_per = [] for intervals in available: max_len = 0 for a, b in intervals: max_len = max(max_len, b - a) max_T_per.append(max_len) min_max_T = min(max_T_per) if min_max_T == 0: print("0/1") return def is_possible(T): earliest = [] latest = [] for intervals in available: earliest_start = None latest_start = None for a, b in intervals: if b - a >= T: if earliest_start is None: earliest_start = a candidate = b - T if latest_start is None or candidate > latest_start: latest_start = candidate if earliest_start is None: return False earliest.append(earliest_start) latest.append(latest_start) from itertools import product for choices in product([0, 1], repeat=n): awake = [] for i in range(n): s = earliest[i] if choices[i] else latest[i] e = s + T for a, b in available[i]: if b <= s or a >= e: awake.append((a, b)) else: if a < s: awake.append((a, s)) if e < b: awake.append((e, b)) awake.sort() merged = [] for a, b in awake: if merged and merged[-1][1] >= a: merged[-1] = (merged[-1][0], max(merged[-1][1], b)) else: merged.append((a, b)) if not merged: continue if merged[0][0] > 0: continue if merged[-1][1] < L: continue prev = 0 valid = True for a, b in merged: if a > prev: valid = False break prev = b if valid and prev >= L: return True return False left = 0.0 right = min_max_T best_num = 0 best_den = 1 eps = 1e-9 for _ in range(100): mid = (left + right) / 2 if is_possible(mid): best_num = mid best_den = 1 left = mid else: right = mid numerator = 0 denominator = 1 for den in range(1, 101): for num in range(0, den * int(min_max_T) + 1): T = Fraction(num, den) if T.numerator == num and T.denominator == den and is_possible(T): if T > Fraction(numerator, denominator): numerator = T.numerator denominator = T.denominator print(f"{numerator}/{denominator}") if __name__ == "__main__": main()
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 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | import sys from fractions import Fraction def main(): n, L = map(int, sys.stdin.readline().split()) schedules = [sys.stdin.readline().strip() for _ in range(n)] available = [] for s in schedules: intervals = [] start = None for i in range(L): if s[i] == '.': if start is None: start = i else: if start is not None: intervals.append((start, i)) start = None if start is not None: intervals.append((start, L)) available.append(intervals) all_available = [] for intervals in available: for a, b in intervals: all_available.extend([(a, True), (b, False)]) all_available.sort(key=lambda x: (x[0], not x[1])) coverage = 0 cnt = 0 last = 0 total_cover = True for pos, is_start in all_available: if cnt == 0 and is_start: if pos > last: total_cover = False break last = pos if is_start: cnt += 1 else: cnt -= 1 if cnt == 0: coverage += pos - last last = pos if last < L: total_cover = False if not total_cover: print(-1) return max_T_per = [] for intervals in available: max_len = 0 for a, b in intervals: max_len = max(max_len, b - a) max_T_per.append(max_len) min_max_T = min(max_T_per) if min_max_T == 0: print("0/1") return def is_possible(T): earliest = [] latest = [] for intervals in available: earliest_start = None latest_start = None for a, b in intervals: if b - a >= T: if earliest_start is None: earliest_start = a candidate = b - T if latest_start is None or candidate > latest_start: latest_start = candidate if earliest_start is None: return False earliest.append(earliest_start) latest.append(latest_start) from itertools import product for choices in product([0, 1], repeat=n): awake = [] for i in range(n): s = earliest[i] if choices[i] else latest[i] e = s + T for a, b in available[i]: if b <= s or a >= e: awake.append((a, b)) else: if a < s: awake.append((a, s)) if e < b: awake.append((e, b)) awake.sort() merged = [] for a, b in awake: if merged and merged[-1][1] >= a: merged[-1] = (merged[-1][0], max(merged[-1][1], b)) else: merged.append((a, b)) if not merged: continue if merged[0][0] > 0: continue if merged[-1][1] < L: continue prev = 0 valid = True for a, b in merged: if a > prev: valid = False break prev = b if valid and prev >= L: return True return False left = 0.0 right = min_max_T best_num = 0 best_den = 1 eps = 1e-9 for _ in range(100): mid = (left + right) / 2 if is_possible(mid): best_num = mid best_den = 1 left = mid else: right = mid numerator = 0 denominator = 1 for den in range(1, 101): for num in range(0, den * int(min_max_T) + 1): T = Fraction(num, den) if T.numerator == num and T.denominator == den and is_possible(T): if T > Fraction(numerator, denominator): numerator = T.numerator denominator = T.denominator print(f"{numerator}/{denominator}") if __name__ == "__main__": main() |