195282025-12-12 17:11:05TtestCsapatás a lócsapattalcpp17Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask20/22
3Wrong answer3ms324 KiB
4Wrong answer3ms316 KiB
5Wrong answer3ms316 KiB
6Wrong answer3ms316 KiB
7Wrong answer3ms316 KiB
8Wrong answer3ms564 KiB
9Wrong answer3ms316 KiB
10Wrong answer3ms508 KiB
11Wrong answer3ms316 KiB
12Wrong answer3ms316 KiB
13Wrong answer3ms316 KiB
14Wrong answer3ms316 KiB
subtask30/17
15Wrong answer3ms324 KiB
16Wrong answer3ms316 KiB
17Wrong answer3ms316 KiB
18Wrong answer3ms316 KiB
19Wrong answer3ms316 KiB
20Wrong answer3ms564 KiB
21Wrong answer3ms316 KiB
22Wrong answer3ms508 KiB
23Wrong answer3ms316 KiB
24Wrong answer3ms316 KiB
25Wrong answer3ms316 KiB
26Wrong answer3ms316 KiB
27Wrong answer1ms316 KiB
28Wrong answer1ms316 KiB
29Accepted1ms316 KiB
30Wrong answer1ms316 KiB
31Accepted1ms564 KiB
32Accepted1ms508 KiB
33Accepted1ms316 KiB
34Wrong answer1ms316 KiB
35Accepted2ms316 KiB
36Accepted1ms512 KiB
37Accepted1ms316 KiB
38Accepted1ms316 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms316 KiB
41Wrong answer1ms316 KiB
42Wrong answer1ms316 KiB
43Wrong answer1ms316 KiB
44Wrong answer1ms316 KiB
45Wrong answer1ms500 KiB
46Wrong answer2ms548 KiB
47Wrong answer1ms564 KiB
48Wrong answer1ms424 KiB
49Accepted1ms316 KiB
50Accepted1ms316 KiB
subtask40/61
51Accepted1ms316 KiB
52Accepted1ms316 KiB
53Wrong answer3ms324 KiB
54Wrong answer3ms316 KiB
55Wrong answer3ms316 KiB
56Wrong answer3ms316 KiB
57Wrong answer3ms316 KiB
58Wrong answer3ms564 KiB
59Wrong answer3ms316 KiB
60Wrong answer3ms508 KiB
61Wrong answer3ms316 KiB
62Wrong answer3ms316 KiB
63Wrong answer3ms316 KiB
64Wrong answer3ms316 KiB
65Wrong answer1ms316 KiB
66Wrong answer1ms316 KiB
67Accepted1ms316 KiB
68Wrong answer1ms316 KiB
69Accepted1ms564 KiB
70Accepted1ms508 KiB
71Accepted1ms316 KiB
72Wrong answer1ms316 KiB
73Accepted2ms316 KiB
74Accepted1ms512 KiB
75Accepted1ms316 KiB
76Accepted1ms316 KiB
77Wrong answer1ms316 KiB
78Wrong answer1ms316 KiB
79Wrong answer1ms316 KiB
80Wrong answer1ms316 KiB
81Wrong answer1ms316 KiB
82Wrong answer1ms316 KiB
83Wrong answer1ms500 KiB
84Wrong answer2ms548 KiB
85Wrong answer1ms564 KiB
86Wrong answer1ms424 KiB
87Accepted1ms316 KiB
88Accepted1ms316 KiB
89Accepted3ms432 KiB
90Accepted3ms316 KiB
91Accepted3ms512 KiB
92Wrong answer3ms316 KiB
93Accepted3ms440 KiB
94Wrong answer3ms508 KiB
95Accepted4ms564 KiB
96Wrong answer4ms316 KiB
97Accepted3ms316 KiB
98Accepted3ms316 KiB
99Accepted3ms500 KiB
100Accepted3ms316 KiB
101Wrong answer3ms316 KiB
102Wrong answer3ms316 KiB
103Wrong answer3ms508 KiB
104Wrong answer4ms316 KiB
105Wrong answer3ms316 KiB
106Accepted3ms316 KiB
107Accepted3ms316 KiB
108Accepted3ms316 KiB
109Wrong answer3ms316 KiB
110Wrong answer3ms436 KiB
111Wrong answer4ms316 KiB
112Wrong answer3ms316 KiB
113Wrong answer4ms316 KiB
114Wrong answer3ms316 KiB
115Wrong answer3ms316 KiB
116Wrong answer3ms436 KiB
117Wrong answer3ms532 KiB