Official

E - Oversleeping Editorial by en_translator


The state of the train and Takahashi transits only at integer times, so it is sufficient to check if Takahashi can get off for each integral time.
Therefore, it is sufficient to solve the following problem: What is the minimum non-negative integer \(t\) such that

  • \(X ≤ t \bmod (2X+2Y) < X + Y\), and
  • \(P ≤ t \bmod (P + Q) < P + Q\)?

Here, \(Y, Q ≤ 500\), which means the train stops at town B for very short time, and so does Takahashi wakes up, we can brute force all \(t \bmod (2X+2Y)\) and \(t \bmod (P + Q)\).
Thus, it is sufficient to solve the following problem:

You are given two integers \(t_1(X ≤ t_1 < X + Y)\) and \(t_2(P ≤ t_2 < P + Q)\). What is the minimum non-negative integer \(t\) such that

  • \(t = t_1 \pmod{2X+2Y}\), and
  • \(t = t_2 \pmod{P + Q}\)?

This can be found in an \(O(\log(X+Y+P+Q))\) time with extended Euclidean algorithm, so the problem can be solved in a total of \(O(YQ\log(X+Y+P+Q))\) time.

For implementation, you can use crt in AC Library.

Sample Code (C++)

#include <bits/stdc++.h>
#include <atcoder/math>
using namespace std;
using ll = int64_t;
const ll INF = numeric_limits<ll>::max() / 4;

void solve(){
    ll X, Y, P, Q;
    cin >> X >> Y >> P >> Q;
    ll ans = INF;
    for(ll t1 = X; t1 < X + Y; t1++) for(ll t2 = P; t2 < P + Q; t2++){
        auto [t, lcm] = atcoder::crt({t1, t2}, {(X + Y) * 2, P + Q});
        if(lcm == 0) continue;
        if(ans > t) ans = t;
    }
    if(ans == INF) puts("infinity");
    else cout << ans << endl;
}
int main(){
    ll T;
    cin >> T;
    while(T--) solve();
}

Sample Code (Python)


BONUS : Solve it in a total of \(O(Y+Q+\log(X+Y+P+Q))\) time!

posted:
last update: