公式

C - Walking Takahashi 解説 by evima


First, if \(X < 0\), it corresponds to the case where we replace \(X := -X\), in which all the directions of movement is reversed, so without loss of generality, we can assume that \(X \geq 0\).

Before considering minimizing, let us consider the possible coordinates \(Y\) after \(K\) moves.

First, after each move, the remainder of the coordinate divided by \(D\) does not change, so it is necessary that \(Y = X \pmod D\). Also, it has to be reachable in \(K\) moves, so it is also necessary to hold that \(\frac{|Y-X|}{D} \leq K\).

Moreover, due to the condition of exactly \(K\) times, it should also hold that \(\frac{|Y-X|}{D} = K \pmod 2\).

This is because, when the coordinate is represented as \(x = p * D + r (p, r \in \mathbb{Z}, 0 \leq r < D)\), the parity of \(p\) changes after every move.

Also, if all those conditions are satisfied, you can finish the move at such \(Y\). This can be achieved by first repeat moving from \(X\) to \(Y\), then move back and forth between coordinates \(Y\) and \(Y-D\) for the remaining moves (whose number will be always an even number).

Therefore, move \(-D\) for \(\lfloor \frac{X}{D} \rfloor\) number of times, and let \(K := K - \lfloor \frac{X}{D} \rfloor\). (If you run out of \(K\) moves halfway, then that coordinate is the answer) Let \(A\) be that coordinate, and if \(K\) is even, output \(A\), or if it is odd, output \(|A-D|\). (If you move back and forth around \(X = 0\), you can always stay in the optimal coordinate due to the property of remainder, and that is why it can be achieved.)

The time complexity is \(\mathrm{O}(1)\).

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    ll X, K, D;
    cin >> X >> K >> D;
    X = abs(X);

    ll straight = min(K, X / D);
    K -= straight;
    X -= straight * D;

    if (K % 2 == 0) {
        cout << X << endl;
    } else {
        cout << D - X << endl;
    }

    return 0;
}

投稿日時:
最終更新: