ABC026 D - 高橋君ボール1号
備忘録
問題
回答
import sys, os, math, bisect, itertools, collections, heapq, queue from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall from decimal import Decimal from collections import defaultdict # import fractions sys.setrecursionlimit(10000000) ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] lcm = lambda x, y: (x * y) // math.gcd(x, y) # lcm = lambda x, y: (x * y) // fractions.gcd(x, y) MOD = 10 ** 9 + 7 MAX = float('inf') def f(A, B, C, t): return A * t + B * math.sin(C * t * math.pi) def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") A, B, C = il() mi, mx = 0, 101 while True: me = (mx + mi) / 2 time = f(A, B, C, me) if str(time).startswith('100.0000000'): break if time > 100: mx = me else: mi = me print(me) if __name__ == '__main__': main()
考え方
ある時間t
のとき、ボールの位置が100
より上回っている場合はt
を少なくし、
ボールの位置が100
を下回っている場合にはt
を大きくする。
小数点も含んだ全ての範囲を普通に探索するのは時間が足りないため、
二分探索を用いてある時間t
の探索を行なう。
初めに、t
が取りうる最小値と最大値より上回る値を用意し(mi, mx = 0, 101
)、
その中央値をt
としたf(t)
を計算する。
f(t)
の結果が100
を上回っている場合には最大値を中央値に変え(mx = me
)、
下回っている場合には最小値を中央値に変える(mi = me
)。
これをf(t)
の結果が100
と一致するまで繰り返すことによって、
ある時間t
を探索することができる。
ちなみに、この問題ではf(t)
の結果に少数が含まれており、
10^-6
まで誤差が許容されているため、
f(t)
の先頭が100.0000000
と一致しているt
を回答とした。