solution_bf.cpp

#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

/*
    Brute-force baseline (intentionally non-optimal):

    Consider each gate position as a node in an unweighted graph.
    From position p, we can go to p + a for every integer a such that:
      - 1 <= a <= m
      - a % k != 0
      - p + a <= x   (must not overshoot, since we need to land exactly on x)

    The minimum number of moves equals the shortest path length from 0 to x,
    which is found via a plain BFS over positions.

    This is correct but can be extremely slow / memory-heavy for large x.
*/

static long long solveOneCase(long long x, long long k, long long m) {
    queue<long long> bfsQueue;
    unordered_map<long long, long long> dist;

    dist[0] = 0;
    bfsQueue.push(0);

    while (!bfsQueue.empty()) {
        long long p = bfsQueue.front();
        bfsQueue.pop();

        long long curDist = dist[p];
        if (p == x) {
            return curDist;
        }

        long long maxJump = min(m, x - p);
        for (long long a = 1; a <= maxJump; a++) {
            if (a % k == 0) {
                continue;
            }
            long long nextPos = p + a;
            if (dist.find(nextPos) == dist.end()) {
                dist[nextPos] = curDist + 1;
                bfsQueue.push(nextPos);
            }
        }
    }

    // With k >= 2, jump length 1 is always allowed, so x is always reachable.
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long x, k, m;
        cin >> x >> k >> m;
        cout << solveOneCase(x, k, m) << "\n";
    }

    return 0;
}