| 19529 | 2025-12-12 17:12:35 | Ttest | Csapatás a lócsapattal | cpp17 | Hibás válasz 0/100 | 4ms | 560 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 1ms | 508 KiB | ||||
| 2 | Elfogadva | 1ms | 316 KiB | ||||
| subtask2 | 0/22 | ||||||
| 3 | Hibás válasz | 3ms | 316 KiB | ||||
| 4 | Hibás válasz | 3ms | 316 KiB | ||||
| 5 | Hibás válasz | 3ms | 316 KiB | ||||
| 6 | Hibás válasz | 3ms | 316 KiB | ||||
| 7 | Hibás válasz | 3ms | 384 KiB | ||||
| 8 | Hibás válasz | 3ms | 316 KiB | ||||
| 9 | Hibás válasz | 3ms | 316 KiB | ||||
| 10 | Hibás válasz | 3ms | 316 KiB | ||||
| 11 | Hibás válasz | 3ms | 316 KiB | ||||
| 12 | Hibás válasz | 3ms | 316 KiB | ||||
| 13 | Hibás válasz | 3ms | 316 KiB | ||||
| 14 | Hibás válasz | 3ms | 316 KiB | ||||
| subtask3 | 0/17 | ||||||
| 15 | Hibás válasz | 3ms | 316 KiB | ||||
| 16 | Hibás válasz | 3ms | 316 KiB | ||||
| 17 | Hibás válasz | 3ms | 316 KiB | ||||
| 18 | Hibás válasz | 3ms | 316 KiB | ||||
| 19 | Hibás válasz | 3ms | 384 KiB | ||||
| 20 | Hibás válasz | 3ms | 316 KiB | ||||
| 21 | Hibás válasz | 3ms | 316 KiB | ||||
| 22 | Hibás válasz | 3ms | 316 KiB | ||||
| 23 | Hibás válasz | 3ms | 316 KiB | ||||
| 24 | Hibás válasz | 3ms | 316 KiB | ||||
| 25 | Hibás válasz | 3ms | 316 KiB | ||||
| 26 | Hibás válasz | 3ms | 316 KiB | ||||
| 27 | Hibás válasz | 1ms | 316 KiB | ||||
| 28 | Hibás válasz | 1ms | 316 KiB | ||||
| 29 | Elfogadva | 1ms | 316 KiB | ||||
| 30 | Hibás válasz | 1ms | 316 KiB | ||||
| 31 | Elfogadva | 2ms | 324 KiB | ||||
| 32 | Elfogadva | 1ms | 552 KiB | ||||
| 33 | Elfogadva | 1ms | 316 KiB | ||||
| 34 | Hibás válasz | 1ms | 316 KiB | ||||
| 35 | Elfogadva | 1ms | 508 KiB | ||||
| 36 | Elfogadva | 1ms | 316 KiB | ||||
| 37 | Elfogadva | 1ms | 500 KiB | ||||
| 38 | Elfogadva | 1ms | 536 KiB | ||||
| 39 | Hibás válasz | 1ms | 316 KiB | ||||
| 40 | Hibás válasz | 1ms | 316 KiB | ||||
| 41 | Hibás válasz | 1ms | 316 KiB | ||||
| 42 | Hibás válasz | 1ms | 560 KiB | ||||
| 43 | Hibás válasz | 1ms | 316 KiB | ||||
| 44 | Hibás válasz | 1ms | 392 KiB | ||||
| 45 | Hibás válasz | 1ms | 332 KiB | ||||
| 46 | Hibás válasz | 1ms | 316 KiB | ||||
| 47 | Hibás válasz | 1ms | 316 KiB | ||||
| 48 | Hibás válasz | 1ms | 316 KiB | ||||
| 49 | Elfogadva | 1ms | 316 KiB | ||||
| 50 | Elfogadva | 1ms | 316 KiB | ||||
| subtask4 | 0/61 | ||||||
| 51 | Elfogadva | 3ms | 508 KiB | ||||
| 52 | Elfogadva | 2ms | 316 KiB | ||||
| 53 | Hibás válasz | 3ms | 316 KiB | ||||
| 54 | Hibás válasz | 3ms | 316 KiB | ||||
| 55 | Hibás válasz | 3ms | 316 KiB | ||||
| 56 | Hibás válasz | 3ms | 316 KiB | ||||
| 57 | Hibás válasz | 3ms | 384 KiB | ||||
| 58 | Hibás válasz | 3ms | 316 KiB | ||||
| 59 | Hibás válasz | 3ms | 316 KiB | ||||
| 60 | Hibás válasz | 3ms | 316 KiB | ||||
| 61 | Hibás válasz | 3ms | 316 KiB | ||||
| 62 | Hibás válasz | 3ms | 316 KiB | ||||
| 63 | Hibás válasz | 3ms | 316 KiB | ||||
| 64 | Hibás válasz | 3ms | 316 KiB | ||||
| 65 | Hibás válasz | 1ms | 316 KiB | ||||
| 66 | Hibás válasz | 1ms | 316 KiB | ||||
| 67 | Elfogadva | 1ms | 316 KiB | ||||
| 68 | Hibás válasz | 1ms | 316 KiB | ||||
| 69 | Elfogadva | 2ms | 324 KiB | ||||
| 70 | Elfogadva | 1ms | 552 KiB | ||||
| 71 | Elfogadva | 1ms | 316 KiB | ||||
| 72 | Hibás válasz | 1ms | 316 KiB | ||||
| 73 | Elfogadva | 1ms | 508 KiB | ||||
| 74 | Elfogadva | 1ms | 316 KiB | ||||
| 75 | Elfogadva | 1ms | 500 KiB | ||||
| 76 | Elfogadva | 1ms | 536 KiB | ||||
| 77 | Hibás válasz | 1ms | 316 KiB | ||||
| 78 | Hibás válasz | 1ms | 316 KiB | ||||
| 79 | Hibás válasz | 1ms | 316 KiB | ||||
| 80 | Hibás válasz | 1ms | 560 KiB | ||||
| 81 | Hibás válasz | 1ms | 316 KiB | ||||
| 82 | Hibás válasz | 1ms | 392 KiB | ||||
| 83 | Hibás válasz | 1ms | 332 KiB | ||||
| 84 | Hibás válasz | 1ms | 316 KiB | ||||
| 85 | Hibás válasz | 1ms | 316 KiB | ||||
| 86 | Hibás válasz | 1ms | 316 KiB | ||||
| 87 | Elfogadva | 1ms | 316 KiB | ||||
| 88 | Elfogadva | 1ms | 316 KiB | ||||
| 89 | Elfogadva | 3ms | 508 KiB | ||||
| 90 | Elfogadva | 3ms | 316 KiB | ||||
| 91 | Elfogadva | 3ms | 316 KiB | ||||
| 92 | Hibás válasz | 3ms | 316 KiB | ||||
| 93 | Elfogadva | 3ms | 316 KiB | ||||
| 94 | Hibás válasz | 3ms | 316 KiB | ||||
| 95 | Elfogadva | 3ms | 316 KiB | ||||
| 96 | Hibás válasz | 3ms | 316 KiB | ||||
| 97 | Elfogadva | 3ms | 344 KiB | ||||
| 98 | Elfogadva | 3ms | 316 KiB | ||||
| 99 | Elfogadva | 3ms | 316 KiB | ||||
| 100 | Elfogadva | 3ms | 316 KiB | ||||
| 101 | Hibás válasz | 3ms | 316 KiB | ||||
| 102 | Hibás válasz | 4ms | 316 KiB | ||||
| 103 | Hibás válasz | 3ms | 316 KiB | ||||
| 104 | Hibás válasz | 3ms | 316 KiB | ||||
| 105 | Hibás válasz | 3ms | 316 KiB | ||||
| 106 | Elfogadva | 3ms | 316 KiB | ||||
| 107 | Elfogadva | 4ms | 316 KiB | ||||
| 108 | Elfogadva | 3ms | 316 KiB | ||||
| 109 | Hibás válasz | 3ms | 316 KiB | ||||
| 110 | Hibás válasz | 3ms | 316 KiB | ||||
| 111 | Hibás válasz | 3ms | 316 KiB | ||||
| 112 | Hibás válasz | 3ms | 316 KiB | ||||
| 113 | Hibás válasz | 3ms | 508 KiB | ||||
| 114 | Hibás válasz | 3ms | 316 KiB | ||||
| 115 | Hibás válasz | 3ms | 316 KiB | ||||
| 116 | Hibás válasz | 3ms | 316 KiB | ||||
| 117 | Hibás válasz | 3ms | 316 KiB | ||||