解けず。筋肉が必要な方針を選んでしまい突破できなかった。

solution

上手く場合分けして周期を有理数$\mathrm{lcm}$。 Euclidの互除法があるので$O(\log \max \{ t_1, t_2, t_3 \})$。

$2$点$P_i, P_j$の位置が一致する時刻$t$に関して、その$2$点の進行方向で分ける。 $v_i = \frac{2L}{t_i}$として:

  • $v_it + v_jt \equiv 0 \pmod{2L}$ iff $P_i, P_j$の位置は一致し進行方向も一致
  • $v_it - v_jt \equiv 0 \pmod{2L}$ iff $P_i, P_j$の位置は一致し進行方向は不一致

つまり$v_1t \pm v_2t \equiv v_2t \pm v_3t \equiv v_3t \pm v_1t \equiv 0 \pmod{2L}$で適当に符号を決め、最小な$t$を選べばよい。

このような$t$は$\mathrm{lcm}$として求まる。 有理数では$\mathrm{lcm}(\frac{p_1}{q_1}, \frac{p_2}{q_2}) = \frac{\mathrm{lcm}(p_1q_2, q_1p_2)}{q_1q_2}$。

implementation

#!/usr/bin/env python3
from fractions import Fraction
import math
def lcm(a, b):
    return a * b // math.gcd(a, b)
def qlcm(p, q):
    a = p.numerator * q.denominator
    b = p.denominator * q.numerator
    c = p.denominator * q.denominator
    return Fraction(lcm(a, b), c)
v1 = Fraction(2, int(input()))
v2 = Fraction(2, int(input()))
v3 = Fraction(2, int(input()))
ans = min([
    qlcm(2 / abs(v1 + v2), qlcm(2 / abs(v2 + v3), 2 / abs(v3 + v1))),
    qlcm(2 / abs(v1 + v2), qlcm(2 / abs(v2 + v3), 2 / abs(v3 - v1))),
    qlcm(2 / abs(v1 + v2), qlcm(2 / abs(v2 - v3), 2 / abs(v3 + v1))),
    qlcm(2 / abs(v1 + v2), qlcm(2 / abs(v2 - v3), 2 / abs(v3 - v1))),
    qlcm(2 / abs(v1 - v2), qlcm(2 / abs(v2 + v3), 2 / abs(v3 + v1))),
    qlcm(2 / abs(v1 - v2), qlcm(2 / abs(v2 + v3), 2 / abs(v3 - v1))),
    qlcm(2 / abs(v1 - v2), qlcm(2 / abs(v2 - v3), 2 / abs(v3 + v1))),
    qlcm(2 / abs(v1 - v2), qlcm(2 / abs(v2 - v3), 2 / abs(v3 - v1))),
    ])
print('%d/%d' % (ans.numerator, ans.denominator))