solution_bf.cpp

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>

using namespace std;

using ull = unsigned long long;

static ull getShownRoom(ull n, ull residue) {
    // residue is assumed to be in [0, L-1] where L = 2*(n-1), n > 1.
    if (n == 1) {
        return 1;
    }
    ull nMinusOne = n - 1;
    ull l = 2 * nMinusOne;

    if (residue <= nMinusOne) {
        return residue + 1;
    }
    return (l - residue) + 1;
}

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

    int t;
    cin >> t;
    while (t--) {
        long long nIn, xIn, yIn, dIn;
        cin >> nIn >> xIn >> yIn >> dIn;

        ull n = static_cast<ull>(nIn);
        ull x = static_cast<ull>(xIn);
        ull y = static_cast<ull>(yIn);
        ull d = static_cast<ull>(dIn);

        // Special case: with one room, the shown room is always 1.
        if (n == 1) {
            cout << 0;
            if (t > 0) cout << "\n";
            continue;
        }

        ull nMinusOne = n - 1;
        ull l = 2 * nMinusOne; // l >= 2 when n > 1

        // Initial hidden coordinate z = x - 1, so residue is (x-1) mod l.
        ull startRes = (x - 1) % l;
        ull step = d % l;

        /*
            Brute-force baseline:
            Enumerate the entire cycle generated by repeatedly adding 'step' modulo l.
            This can be extremely slow for large n (l up to ~2e18), but is correct.
        */

        // Compute cycle length (the number of additions needed to return to startRes).
        ull cycleLen = 0;
        {
            ull res = startRes;
            do {
                res = (res + step) % l;
                cycleLen++;
            } while (res != startRes);
        }

        // Scan all residues in the cycle and track the minimum button presses.
        const ull inf = numeric_limits<ull>::max();
        ull best = inf;

        ull res = startRes;
        for (ull k = 0; k < cycleLen; k++) {
            ull shown = getShownRoom(n, res);
            if (shown == y) {
                // k forward presses reaches this residue; cycleLen-k backward presses also reaches it.
                ull presses = min(k, cycleLen - k);
                best = min(best, presses);
            }
            res = (res + step) % l;
        }

        if (best == inf) {
            cout << -1;
        } else {
            cout << best;
        }
        if (t > 0) cout << "\n";
    }

    return 0;
}