195292025-12-12 17:12:35TtestCsapatás a lócsapattalcpp17Hibás válasz 0/1004ms560 KiB
#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

// Segédfüggvény a legnagyobb közös osztóhoz (C++17-ben std::gcd is jó, de biztosra megyünk)
long long my_gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

// Struktúra egy intervallum tárolására [start, end]
struct Interval {
    long long start, end;
    bool empty;
};

// Visszaadja a "rossz" intervallumot: azon koordinátákat [0, dim-1]-ben,
// ahonnan NEM lehet 'step' méretût lépni (sem jobbra, sem balra).
// Rossz, ha: x + step >= dim  ÉS  x - step < 0
Interval get_bad_interval(long long dim, long long step) {
    long long s = max(0LL, dim - step);
    long long e = min(dim - 1, step - 1);
    if (s > e) {
        return {0, 0, true}; // Üres intervallum (nincs rossz mezõ)
    }
    return {s, e, false};
}

// Két intervallum metszetét vizsgálja. Igaz, ha a metszet NEM üres.
bool intervals_intersect(Interval a, Interval b) {
    if (a.empty || b.empty) return false;
    long long s = max(a.start, b.start);
    long long e = min(a.end, b.end);
    return s <= e;
}

void solve() {
    long long N, M, H, W;
    if (!(cin >> N >> M >> H >> W)) return;

    // 1. Alapesetek
    // Ha 1x1-es a tábla, már ott vagyunk mindenhol.
    if (N == 1 && M == 1) {
        cout << "YES" << endl;
        return;
    }
    // Ha a tábla 1 dimenziós (de nem 1x1), és van bármilyen lépéskényszer (W,H >= 1),
    // akkor nem tudunk elmozdulni a vonalról anélkül, hogy leessünk.
    if (N == 1 || M == 1) {
        cout << "NO" << endl;
        return;
    }

    // 2. Paritás ellenõrzése
    // Ha H+W páros, a (x+y) paritása sosem változik (vagy mindig változik ugyanúgy),
    // így a tábla fele elérhetetlen (mint a futó a sakkban, vagy a huszár, ha nem váltana színt).
    if ((H + W) % 2 == 0) {
        cout << "NO" << endl;
        return;
    }

    // 3. LNKO ellenõrzése
    // Ha gcd(H, W) > 1, akkor a koordináták mindig a gcd többszöröseivel változnak.
    if (my_gcd(H, W) > 1) {
        cout << "NO" << endl;
        return;
    }

    // 4. Szûk sávok (Narrow Strip) ellenõrzése
    // Ha az egyik dimenzióban (pl N) nem tudunk H-t lépni, akkor abban az irányban
    // csak W-t léphetünk. Ez azt jelenti, hogy a MÁSIK dimenzióban (M) mindig H-t kell lépnünk.
    // Ha H > 1, akkor a másik dimenzióban nem érünk el minden sort.
    if (N <= H && H > 1) { cout << "NO" << endl; return; }
    if (N <= W && W > 1) { cout << "NO" << endl; return; }
    if (M <= H && H > 1) { cout << "NO" << endl; return; }
    if (M <= W && W > 1) { cout << "NO" << endl; return; }

    // 5. Izolált mezõk (Dead Squares)
    // Megnézzük, vannak-e olyan mezõk, ahonnan semelyik típusú ugrás nem hajtható végre.
    // Ugrás 1: x-ben W, y-ban H. (Tiltva, ha x a bad_X_W-ben VAGY y a bad_Y_H-ban van)
    // Ugrás 2: x-ben H, y-ban W. (Tiltva, ha x a bad_X_H-ban VAGY y a bad_Y_W-ben van)

    Interval bx_w = get_bad_interval(N, W); // Rossz X-ek W lépéshez
    Interval bx_h = get_bad_interval(N, H); // Rossz X-ek H lépéshez
    Interval by_w = get_bad_interval(M, W); // Rossz Y-ok W lépéshez
    Interval by_h = get_bad_interval(M, H); // Rossz Y-ok H lépéshez

    // Akkor van baj, ha a két feltételrendszer metszete nem üres.
    // A logikai feltétel: (x in bx_w OR y in by_h) AND (x in bx_h OR y in by_w)
    // Ezt szétbontva 4 eset lehetséges (disztributivitás):

    bool has_isolated = false;

    // Eset 1: x mindkét lépéshez rossz (x in bx_w AND x in bx_h)
    if (intervals_intersect(bx_w, bx_h)) has_isolated = true;

    // Eset 2: y mindkét lépéshez rossz (y in by_h AND y in by_w)
    if (intervals_intersect(by_h, by_w)) has_isolated = true;

    // Eset 3: Ugrás 1 x miatt rossz, Ugrás 2 y miatt rossz (x in bx_w AND y in by_w)
    // Ez egy téglalap alakú terület a táblán. Ha mindkét intervallum létezik, akkor a téglalap létezik.
    if (!bx_w.empty && !by_w.empty) has_isolated = true;

    // Eset 4: Ugrás 1 y miatt rossz, Ugrás 2 x miatt rossz (y in by_h AND x in bx_h)
    if (!by_h.empty && !bx_h.empty) has_isolated = true;

    if (has_isolated) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}

int main() {
    // Gyors I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms508 KiB
2Elfogadva1ms316 KiB
subtask20/22
3Hibás válasz3ms316 KiB
4Hibás válasz3ms316 KiB
5Hibás válasz3ms316 KiB
6Hibás válasz3ms316 KiB
7Hibás válasz3ms384 KiB
8Hibás válasz3ms316 KiB
9Hibás válasz3ms316 KiB
10Hibás válasz3ms316 KiB
11Hibás válasz3ms316 KiB
12Hibás válasz3ms316 KiB
13Hibás válasz3ms316 KiB
14Hibás válasz3ms316 KiB
subtask30/17
15Hibás válasz3ms316 KiB
16Hibás válasz3ms316 KiB
17Hibás válasz3ms316 KiB
18Hibás válasz3ms316 KiB
19Hibás válasz3ms384 KiB
20Hibás válasz3ms316 KiB
21Hibás válasz3ms316 KiB
22Hibás válasz3ms316 KiB
23Hibás válasz3ms316 KiB
24Hibás válasz3ms316 KiB
25Hibás válasz3ms316 KiB
26Hibás válasz3ms316 KiB
27Hibás válasz1ms316 KiB
28Hibás válasz1ms316 KiB
29Elfogadva1ms316 KiB
30Hibás válasz1ms316 KiB
31Elfogadva2ms324 KiB
32Elfogadva1ms552 KiB
33Elfogadva1ms316 KiB
34Hibás válasz1ms316 KiB
35Elfogadva1ms508 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms500 KiB
38Elfogadva1ms536 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz1ms316 KiB
41Hibás válasz1ms316 KiB
42Hibás válasz1ms560 KiB
43Hibás válasz1ms316 KiB
44Hibás válasz1ms392 KiB
45Hibás válasz1ms332 KiB
46Hibás válasz1ms316 KiB
47Hibás válasz1ms316 KiB
48Hibás válasz1ms316 KiB
49Elfogadva1ms316 KiB
50Elfogadva1ms316 KiB
subtask40/61
51Elfogadva3ms508 KiB
52Elfogadva2ms316 KiB
53Hibás válasz3ms316 KiB
54Hibás válasz3ms316 KiB
55Hibás válasz3ms316 KiB
56Hibás válasz3ms316 KiB
57Hibás válasz3ms384 KiB
58Hibás válasz3ms316 KiB
59Hibás válasz3ms316 KiB
60Hibás válasz3ms316 KiB
61Hibás válasz3ms316 KiB
62Hibás válasz3ms316 KiB
63Hibás válasz3ms316 KiB
64Hibás válasz3ms316 KiB
65Hibás válasz1ms316 KiB
66Hibás válasz1ms316 KiB
67Elfogadva1ms316 KiB
68Hibás válasz1ms316 KiB
69Elfogadva2ms324 KiB
70Elfogadva1ms552 KiB
71Elfogadva1ms316 KiB
72Hibás válasz1ms316 KiB
73Elfogadva1ms508 KiB
74Elfogadva1ms316 KiB
75Elfogadva1ms500 KiB
76Elfogadva1ms536 KiB
77Hibás válasz1ms316 KiB
78Hibás válasz1ms316 KiB
79Hibás válasz1ms316 KiB
80Hibás válasz1ms560 KiB
81Hibás válasz1ms316 KiB
82Hibás válasz1ms392 KiB
83Hibás válasz1ms332 KiB
84Hibás válasz1ms316 KiB
85Hibás válasz1ms316 KiB
86Hibás válasz1ms316 KiB
87Elfogadva1ms316 KiB
88Elfogadva1ms316 KiB
89Elfogadva3ms508 KiB
90Elfogadva3ms316 KiB
91Elfogadva3ms316 KiB
92Hibás válasz3ms316 KiB
93Elfogadva3ms316 KiB
94Hibás válasz3ms316 KiB
95Elfogadva3ms316 KiB
96Hibás válasz3ms316 KiB
97Elfogadva3ms344 KiB
98Elfogadva3ms316 KiB
99Elfogadva3ms316 KiB
100Elfogadva3ms316 KiB
101Hibás válasz3ms316 KiB
102Hibás válasz4ms316 KiB
103Hibás válasz3ms316 KiB
104Hibás válasz3ms316 KiB
105Hibás válasz3ms316 KiB
106Elfogadva3ms316 KiB
107Elfogadva4ms316 KiB
108Elfogadva3ms316 KiB
109Hibás válasz3ms316 KiB
110Hibás válasz3ms316 KiB
111Hibás válasz3ms316 KiB
112Hibás válasz3ms316 KiB
113Hibás válasz3ms508 KiB
114Hibás válasz3ms316 KiB
115Hibás válasz3ms316 KiB
116Hibás válasz3ms316 KiB
117Hibás válasz3ms316 KiB