Programozás‎ > ‎Feladatok‎ > ‎

Kitöltés téglalapokkal

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