Egy nevezetes problémát kell számítógéppel megoldanunk: adott egy n x m -es téglalap, és szeretnénk hézagmentesen, átfedés nélkül lefedni a x b méretű csempékkel. Döntsük el, hogy lehetséges-e a lefedés! A csempék "vízszintesen" és "függőlegesen" is lerakhatók.
Feladat
Írjunk programot, ami eldönti, hogy létezik-e megfelelő csempézés! (Ráadás: ha van, akkor rajzoljunk ki egyet!)
Bemenet
A bemenet első sora a tesztesetek T számát adja meg ( T <= 100), minden további sora pedig egy-egy feladat n, m, a és b értékét. 1<= n, m <= 400; 1 <= a, b <= 100.
Kimenet
A kimenet minden sora az igen vagy nem szót tartalmazza, aszerint, hogy létezik-e megfelelő lefedés az adott tesztesetben.
Példa
Bemenet |
Kimenet |
3 8 8 2 1 8 8 3 1 6 6 1 4 | igen nem nem
|
Tesztadatok
Címkék
A feladat forrása: saját feladat
Algoritmusok: matematikai ismeretek, visszalépéses keresés, pontos fedés
|