195282025-12-12 17:11:05TtestCsapatás a lócsapattalcpp17Hibás válasz 0/1004ms564 KiB
#include <iostream>
#include <algorithm>
#include <numeric> // std::gcd

using namespace std;

int gcd(int a, int b) {
	// Find Minimum of a and b
    int res = min(a, b);

  	// Testing divisiblity with all numbers starting from
	// min(a, b) to 1

    while (res > 1) {

        // If any number divide both a and b, so we
        // got the answer
        if (a % res == 0 && b % res == 0)
            break;
        res--;
    }
	return res;
}


// Intervallum struktúra a "rossz" sávok kezelésére
struct Interval {
    long long start;
    long long end;
    bool empty;

    Interval() : start(0), end(-1), empty(true) {}
    Interval(long long s, long long e) : start(s), end(e), empty(false) {
        if (start > end) empty = true;
    }
};

// Kiszámolja azt az intervallumot [0, dim-1]-en belül,
// ahonnan NEM lehet 'step' nagyságút lépni (mert lelépnénk a tábláról).
// Matematikailag: x + step >= dim ÉS x - step < 0
Interval getBadInterval(long long dim, long long step) {
    long long s = max(0LL, dim - step);
    long long e = min(dim - 1, step - 1);
    return Interval(s, e);
}

// Két intervallum metszete
Interval intersect(Interval a, Interval b) {
    if (a.empty || b.empty) return Interval();
    return Interval(max(a.start, b.start), min(a.end, b.end));
}

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

    // 1. ALAP KIVÉTELEK
    // Ha 1x1-es a tábla, minden mezõ (az az egy) elérve.
    if (N == 1 && M == 1) {
        cout << "YES" << endl;
        return;
    }
    // Ha a tábla 1 dimenziós, de nem 1x1, és a lépések >= 1, akkor lehetetlen.
    // (Mivel a feladat szerint H, W >= 1, nem tudunk "helyben maradni" az 1 széles dimenzióban)
    if (N == 1 || M == 1) {
        cout << "NO" << endl;
        return;
    }

    // 2. MATEMATIKAI FELTÉTELEK
    // Paritás: W+H összegnek páratlannak kell lennie (hogy színt váltson).
    if ((W + H) % 2 == 0) {
        cout << "NO" << endl;
        return;
    }
    // LNKO: Relatív prímeknek kell lenniük.
    if (gcd(W, H) > 1) {
        cout << "NO" << endl;
        return;
    }

    // 3. GEOMETRIAI BLOKKOK (IZOLÁLT MEZÕK)
    // bx_w: Azok az x koordináták, ahonnan nem lehet W-t lépni x-irányban.
    Interval bx_w = getBadInterval(N, W);
    Interval bx_h = getBadInterval(N, H);
    Interval by_w = getBadInterval(M, W);
    Interval by_h = getBadInterval(M, H);

    // Kétféle lépés van:
    // Type 1: dx = W, dy = H (tiltva, ha x in bx_w VAGY y in by_h)
    // Type 2: dx = H, dy = W (tiltva, ha x in bx_h VAGY y in by_w)

    // Akkor van baj, ha létezik olyan (x, y) mezõ, ahonnan se Type 1, se Type 2 nem lehetséges.
    // Halmazelméletileg: (Zone1) metszet (Zone2) != üres.
    // Zone1 = (bx_w sorok) U (by_h oszlopok)
    // Zone2 = (bx_h sorok) U (by_w oszlopok)
    // A metszet 4 részbõl állhat:

    bool isolated = false;

    // 1. eset: x mindkét irányú ugráshoz rossz sávban van
    if (!intersect(bx_w, bx_h).empty) isolated = true;

    // 2. eset: y mindkét irányú ugráshoz rossz sávban van
    if (!intersect(by_w, by_h).empty) isolated = true;

    // 3. eset: x rossz a Type 1-hez, y rossz a Type 2-höz (keresztmetszet)
    if (!bx_w.empty && !by_w.empty) isolated = true;

    // 4. eset: y rossz a Type 1-hez, x rossz a Type 2-höz (keresztmetszet)
    if (!bx_h.empty && !by_h.empty) isolated = true;

    if (isolated) {
        cout << "NO" << endl;
        return;
    }

    // 4. KÉNYSZERPÁLYÁK (NARROW STRIP)
    // Ha az egyik dimenzió túl kicsi egy bizonyos lépéshez, kénytelenek vagyunk
    // a másik típusú lépést használni. Ha az a lépés a másik dimenzióban > 1,
    // akkor átugrunk sorokat/oszlopokat.

    // Ha N <= W, akkor x-ben nem léphetünk W-t. Csak Type 2 (dx=H, dy=W) maradt.
    // Ekkor y mindig W-vel változik. Ha W > 1, nem érünk el mindent.
    if (N <= W && W > 1) {
        cout << "NO" << endl;
        return;
    }
    // Ha N <= H, akkor x-ben nem léphetünk H-t. Csak Type 1 (dx=W, dy=H) maradt.
    // Ekkor y mindig H-val változik. Ha H > 1, nem érünk el mindent.
    if (N <= H && H > 1) {
        cout << "NO" << endl;
        return;
    }
    // Ugyanez M dimenzióra:
    if (M <= W && W > 1) {
        cout << "NO" << endl;
        return;
    }
    if (M <= H && H > 1) {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
}

int main() {
    // Gyors I/O beállítása
    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
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
subtask20/22
3Hibás válasz3ms324 KiB
4Hibás válasz3ms316 KiB
5Hibás válasz3ms316 KiB
6Hibás válasz3ms316 KiB
7Hibás válasz3ms316 KiB
8Hibás válasz3ms564 KiB
9Hibás válasz3ms316 KiB
10Hibás válasz3ms508 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álasz3ms324 KiB
16Hibás válasz3ms316 KiB
17Hibás válasz3ms316 KiB
18Hibás válasz3ms316 KiB
19Hibás válasz3ms316 KiB
20Hibás válasz3ms564 KiB
21Hibás válasz3ms316 KiB
22Hibás válasz3ms508 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
31Elfogadva1ms564 KiB
32Elfogadva1ms508 KiB
33Elfogadva1ms316 KiB
34Hibás válasz1ms316 KiB
35Elfogadva2ms316 KiB
36Elfogadva1ms512 KiB
37Elfogadva1ms316 KiB
38Elfogadva1ms316 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz1ms316 KiB
41Hibás válasz1ms316 KiB
42Hibás válasz1ms316 KiB
43Hibás válasz1ms316 KiB
44Hibás válasz1ms316 KiB
45Hibás válasz1ms500 KiB
46Hibás válasz2ms548 KiB
47Hibás válasz1ms564 KiB
48Hibás válasz1ms424 KiB
49Elfogadva1ms316 KiB
50Elfogadva1ms316 KiB
subtask40/61
51Elfogadva1ms316 KiB
52Elfogadva1ms316 KiB
53Hibás válasz3ms324 KiB
54Hibás válasz3ms316 KiB
55Hibás válasz3ms316 KiB
56Hibás válasz3ms316 KiB
57Hibás válasz3ms316 KiB
58Hibás válasz3ms564 KiB
59Hibás válasz3ms316 KiB
60Hibás válasz3ms508 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
69Elfogadva1ms564 KiB
70Elfogadva1ms508 KiB
71Elfogadva1ms316 KiB
72Hibás válasz1ms316 KiB
73Elfogadva2ms316 KiB
74Elfogadva1ms512 KiB
75Elfogadva1ms316 KiB
76Elfogadva1ms316 KiB
77Hibás válasz1ms316 KiB
78Hibás válasz1ms316 KiB
79Hibás válasz1ms316 KiB
80Hibás válasz1ms316 KiB
81Hibás válasz1ms316 KiB
82Hibás válasz1ms316 KiB
83Hibás válasz1ms500 KiB
84Hibás válasz2ms548 KiB
85Hibás válasz1ms564 KiB
86Hibás válasz1ms424 KiB
87Elfogadva1ms316 KiB
88Elfogadva1ms316 KiB
89Elfogadva3ms432 KiB
90Elfogadva3ms316 KiB
91Elfogadva3ms512 KiB
92Hibás válasz3ms316 KiB
93Elfogadva3ms440 KiB
94Hibás válasz3ms508 KiB
95Elfogadva4ms564 KiB
96Hibás válasz4ms316 KiB
97Elfogadva3ms316 KiB
98Elfogadva3ms316 KiB
99Elfogadva3ms500 KiB
100Elfogadva3ms316 KiB
101Hibás válasz3ms316 KiB
102Hibás válasz3ms316 KiB
103Hibás válasz3ms508 KiB
104Hibás válasz4ms316 KiB
105Hibás válasz3ms316 KiB
106Elfogadva3ms316 KiB
107Elfogadva3ms316 KiB
108Elfogadva3ms316 KiB
109Hibás válasz3ms316 KiB
110Hibás válasz3ms436 KiB
111Hibás válasz4ms316 KiB
112Hibás válasz3ms316 KiB
113Hibás válasz4ms316 KiB
114Hibás válasz3ms316 KiB
115Hibás válasz3ms316 KiB
116Hibás válasz3ms436 KiB
117Hibás válasz3ms532 KiB