A - Jogging Editorial by en_translator
Takahashi repeats the same move at the period of \((A+C)\) seconds. Specifically, for a non-negative integer \(k\), Takahashi’s move between \(k\) and \(k+1\) seconds passed since he started will be:
- walks \(B\) meters, if the remainder of \(k\) divided by \(A+C\) is less than \(A\); or
- stops moving otherwise.
Similarly, Aoki’s move will be:
- walks \(E\) meters, if the remainder of \(k\) divided by \(D+F\) is less than \(D\); or
- stops moving otherwise.
By simulating the moves for each \(k = 0, 1, \dots, X - 1\), we can compute how many meters the two advanced. Therefore, the problem has been solved in a total time complexity of \(O(X)\).
Sample code (C++):
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, d, e, f, x;
cin >> a >> b >> c >> d >> e >> f >> x;
int takahashi = 0, aoki = 0;
for (int k = 0; k < x; ++k) {
if (k % (a + c) < a) {
takahashi += b;
}
if (k % (d + f) < d) {
aoki += e;
}
}
if (takahashi > aoki) {
cout << "Takahashi\n";
} else if (takahashi < aoki) {
cout << "Aoki\n";
} else {
cout << "Draw\n";
}
return 0;
}
This problem can be solved in a faster way (in a total time complexity of \(O(1)\).
Let’s consider every \((A+C)\)-second chunk of Takahashi’s move as a single period. Takahashi advances \(A \times B\) in every period. In the first \(k\) seconds (\(0 \leq k \leq A + C\)) of a period, he advances \(\min(A, k) \times B\) meters.
Suppose that Takahashi completes exactly \(q\) periods during the first \(X\) seconds since he starts, then \(q =\left\lfloor \frac{X}{A + C} \right\rfloor\). The remaining \(X - (A + C) \times q\) seconds belongs to the same period, so the sum of distance Takahashi advances in the first \(X\) seconds is \(A \times B \times q + \min(A, X - (A + C) \times q) \times B\) meters.
The same applies for Aoki, so the distances that the two advance can be calculated in a constant time.
Sample code (Python):
def solve(a, b, c, x):
q = x // (a + c)
r = x % (a + c);
return (q * a + min(a, r)) * b;
a, b, c, d, e, f, x = map(int, input().split())
takahashi = solve(a, b, c, x)
aoki = solve(d, e, f, x)
if takahashi > aoki:
print("Takahashi")
elif takahashi < aoki:
print("Aoki")
else:
print("Draw")
posted:
last update: