diff options
Diffstat (limited to '6_2023.py')
-rw-r--r-- | 6_2023.py | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/6_2023.py b/6_2023.py new file mode 100644 index 0000000..cb8b279 --- /dev/null +++ b/6_2023.py @@ -0,0 +1,59 @@ +import sys +import re +from collections import defaultdict + +D = open(sys.argv[1]).read().strip() +L = D.split("\n") +ans = 0 + +t, d = L +times = [int(x) for x in t.split(":")[1].split()] +dist = [int(x) for x in d.split(":")[1].split()] + +T = "" +for t in times: + T += str(t) +T = int(T) +D = "" +for d in dist: + D += str(d) +D = int(D) + + +def f(t, d): + # runs in O(log(t)) + # let g(x) = x*(t-x) is maximized at t//2 + # we want to know: what is the lowest value s.t. g(x) >= d + # we want to know: what is the highest value s.t. g(x) >= d + def g(x): + return x * (t - x) + + lo = 0 + hi = t // 2 + if hi * (t - hi) < d: + return 0 + assert g(lo) < d and g(hi) >= d + while lo + 1 < hi: + m = (lo + hi) // 2 + if g(m) >= d: + hi = m + else: + lo = m + assert lo + 1 == hi + assert g(lo) < d and g(hi) >= d + first = hi + assert g(first) >= d and g(first - 1) < d + + # g(x) == g(t-x), so there's symmetry about the midpoint t/2 + last = int((t / 2) + (t / 2 - first)) + assert ( + g(last) >= d and g(last + 1) < d + ), f"last={last} g(last)={g(last)} {g(last+1)} d={d}" + return last - first + 1 + + +ans = 1 +for i in range(len(times)): + ans *= f(times[i], dist[i]) +print(ans) +print(f(T, D)) |