Various Programming Challenge Solutions
I don't provide the full problem specifications on this page due to possible copyright issues. Links to the original problem specs are provided below along with the date accessed, which should allow you to use Internet Archive if the original URL hosting a problem specification ever meaningfully changes.
Kattis: Need for Speed [Spec] (2024-03-21)
This problem was solved in the context of competitive programming practice, solving problems in a group setting. I was the writer, but other members of the group provided the vast majority of the thinking/solving.
The group’s original solution:
#!/usr/bin/env python3
from sys import stdin
(n, t) = [int(s) for s in stdin.readline().strip().split()]
data = [[int(x) for x in s.strip().split()] for s in stdin.readlines()]
"""
speed = dist / time
time = dist / speed
"""
(lo, hi) = (float(-1e7), float(1e7))
#print(lo, hi)
#(lo, hi) = (-1000.0, 1000.0)
#for _ in range(8):
#while True:
while hi - lo >= 1e-7:
#print(lo, hi)
c = (hi + lo) / 2
this_t = 0
for dist, speed in data:
speed2 = speed + c
if speed2 <= 0:
this_t = 2 * t # arbitrary large value
break
this_t += dist / speed2
if abs(this_t - t) <= 1e-7:
break
elif this_t > t:
lo = c
else:
hi = c
print((hi + lo) / 2)
I also did a little bit of cleanup afterwards on my own for a nicer solution:
#!/usr/bin/env python3
from sys import stdin
(n, t) = [int(s) for s in stdin.readline().strip().split()]
data = [[int(x) for x in s.strip().split()] for s in stdin.readlines()]
(lo, hi) = (float(-1e7), float(1e7))
while hi - lo >= 1e-7:
c = (hi + lo) / 2
real_t = 0
for dist, speed in data:
real_speed = speed + c
if real_speed <= 0:
real_t = 2 * t # arbitrary large value
break
# speed = dist / time --> time = dist / speed
real_t += dist / real_speed
if real_t > t:
lo = c
else:
hi = c
print(lo)