| 19528 | 2025-12-12 17:11:05 | Ttest | Csapatás a lócsapattal | cpp17 | Hibás válasz 0/100 | 4ms | 564 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 1ms | 316 KiB | ||||
| 2 | Elfogadva | 1ms | 316 KiB | ||||
| subtask2 | 0/22 | ||||||
| 3 | Hibás válasz | 3ms | 324 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 | 316 KiB | ||||
| 8 | Hibás válasz | 3ms | 564 KiB | ||||
| 9 | Hibás válasz | 3ms | 316 KiB | ||||
| 10 | Hibás válasz | 3ms | 508 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 | 324 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 | 316 KiB | ||||
| 20 | Hibás válasz | 3ms | 564 KiB | ||||
| 21 | Hibás válasz | 3ms | 316 KiB | ||||
| 22 | Hibás válasz | 3ms | 508 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 | 1ms | 564 KiB | ||||
| 32 | Elfogadva | 1ms | 508 KiB | ||||
| 33 | Elfogadva | 1ms | 316 KiB | ||||
| 34 | Hibás válasz | 1ms | 316 KiB | ||||
| 35 | Elfogadva | 2ms | 316 KiB | ||||
| 36 | Elfogadva | 1ms | 512 KiB | ||||
| 37 | Elfogadva | 1ms | 316 KiB | ||||
| 38 | Elfogadva | 1ms | 316 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 | 316 KiB | ||||
| 43 | Hibás válasz | 1ms | 316 KiB | ||||
| 44 | Hibás válasz | 1ms | 316 KiB | ||||
| 45 | Hibás válasz | 1ms | 500 KiB | ||||
| 46 | Hibás válasz | 2ms | 548 KiB | ||||
| 47 | Hibás válasz | 1ms | 564 KiB | ||||
| 48 | Hibás válasz | 1ms | 424 KiB | ||||
| 49 | Elfogadva | 1ms | 316 KiB | ||||
| 50 | Elfogadva | 1ms | 316 KiB | ||||
| subtask4 | 0/61 | ||||||
| 51 | Elfogadva | 1ms | 316 KiB | ||||
| 52 | Elfogadva | 1ms | 316 KiB | ||||
| 53 | Hibás válasz | 3ms | 324 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 | 316 KiB | ||||
| 58 | Hibás válasz | 3ms | 564 KiB | ||||
| 59 | Hibás válasz | 3ms | 316 KiB | ||||
| 60 | Hibás válasz | 3ms | 508 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 | 1ms | 564 KiB | ||||
| 70 | Elfogadva | 1ms | 508 KiB | ||||
| 71 | Elfogadva | 1ms | 316 KiB | ||||
| 72 | Hibás válasz | 1ms | 316 KiB | ||||
| 73 | Elfogadva | 2ms | 316 KiB | ||||
| 74 | Elfogadva | 1ms | 512 KiB | ||||
| 75 | Elfogadva | 1ms | 316 KiB | ||||
| 76 | Elfogadva | 1ms | 316 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 | 316 KiB | ||||
| 81 | Hibás válasz | 1ms | 316 KiB | ||||
| 82 | Hibás válasz | 1ms | 316 KiB | ||||
| 83 | Hibás válasz | 1ms | 500 KiB | ||||
| 84 | Hibás válasz | 2ms | 548 KiB | ||||
| 85 | Hibás válasz | 1ms | 564 KiB | ||||
| 86 | Hibás válasz | 1ms | 424 KiB | ||||
| 87 | Elfogadva | 1ms | 316 KiB | ||||
| 88 | Elfogadva | 1ms | 316 KiB | ||||
| 89 | Elfogadva | 3ms | 432 KiB | ||||
| 90 | Elfogadva | 3ms | 316 KiB | ||||
| 91 | Elfogadva | 3ms | 512 KiB | ||||
| 92 | Hibás válasz | 3ms | 316 KiB | ||||
| 93 | Elfogadva | 3ms | 440 KiB | ||||
| 94 | Hibás válasz | 3ms | 508 KiB | ||||
| 95 | Elfogadva | 4ms | 564 KiB | ||||
| 96 | Hibás válasz | 4ms | 316 KiB | ||||
| 97 | Elfogadva | 3ms | 316 KiB | ||||
| 98 | Elfogadva | 3ms | 316 KiB | ||||
| 99 | Elfogadva | 3ms | 500 KiB | ||||
| 100 | Elfogadva | 3ms | 316 KiB | ||||
| 101 | Hibás válasz | 3ms | 316 KiB | ||||
| 102 | Hibás válasz | 3ms | 316 KiB | ||||
| 103 | Hibás válasz | 3ms | 508 KiB | ||||
| 104 | Hibás válasz | 4ms | 316 KiB | ||||
| 105 | Hibás válasz | 3ms | 316 KiB | ||||
| 106 | Elfogadva | 3ms | 316 KiB | ||||
| 107 | Elfogadva | 3ms | 316 KiB | ||||
| 108 | Elfogadva | 3ms | 316 KiB | ||||
| 109 | Hibás válasz | 3ms | 316 KiB | ||||
| 110 | Hibás válasz | 3ms | 436 KiB | ||||
| 111 | Hibás válasz | 4ms | 316 KiB | ||||
| 112 | Hibás válasz | 3ms | 316 KiB | ||||
| 113 | Hibás válasz | 4ms | 316 KiB | ||||
| 114 | Hibás válasz | 3ms | 316 KiB | ||||
| 115 | Hibás válasz | 3ms | 316 KiB | ||||
| 116 | Hibás válasz | 3ms | 436 KiB | ||||
| 117 | Hibás válasz | 3ms | 532 KiB | ||||