summaryrefslogtreecommitdiff
path: root/6_2023.py
diff options
context:
space:
mode:
Diffstat (limited to '6_2023.py')
-rw-r--r--6_2023.py59
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))