În acest prim articol vom prezenta o serie de probleme apărute la concursurile de programare care au o tematică similară şi anume aceea de acoperire în plan. În general acest tip de probleme sunt $NP complete$, dar pentru cazurile particulare prezentate problemele sunt rezolvabile. Cea de a doua parte a articolului o puteţi găsi în "$secţiunea următoare...$":probleme-de-acoperire2.

h2(#prob1ema1). Problema 1 ( _Olimpiada de informatică, Bucureşti, etapa pe sector, 1995,_ [1] )

h2(#problema1). Problema 1 ( _Olimpiada de informatică, Bucureşti, etapa pe sector, 1995,_ [1] )

bq. Se dă un pătrat de latură $2^n^$ care se împarte în pătrate disjuncte de latură $1$. Unul dintre aceste pătrate se elimină. Se cere acoperirea suprafeţei rămase cu piese de forma:

Se vede clar acum, cum prin metoda $divide et impera$ putem să acoperim întreg pătratul cu piesele cerute.

h2(#prob1ema2). Problema 2 ( _Lot 2001,_ [1] )

h2(#problema2). Problema 2 ( _Lot 2001,_ [1] )

bq. Se dă un pătrat de latură $6N + 1$ care se împarte în pătrate disjuncte de latură $1$. Unul dintre aceste pătrate se elimină. Se cere acoperirea suprafeţei rămase cu piese de forma:

p=. !probleme-de-acoperire-1?P22.jpg!

h2(#prob1ema3). Problema 3 ( _Concursul naţional de informatică Lugoj, 1998_ )

h2(#problema3). Problema 3 ( _Concursul naţional de informatică Lugoj, 1998_ )

bq. Să se acopere complet un pătrat de latură $N >= 6$ cu următoarele piese, astfel ca fiecare piesă să fie folosită cel puţin o dată.

p=. !probleme-de-acoperire-1?P33.jpg!

h2(#prob1ema4). Problema 4

h2(#problema4). Problema 4

bq. Să se determine dacă putem acoperi o tablă de dimensiune $N x N$ cu dominouri după ce îi eliminăm două colţuri opuse.

Orice domino amplasat pe tablă va acoperi două pătrăţele de culori diferite, deci tabla trebuie să aibă un număr egal de pătrăţele colorate alb şi negru, fapt care nu se întâmplă în problema noastră. De aici deducem că nu putem acoperi tabla din care au fost eliminate două colţuri opuse. O problemă ce se poate aborda cu o tehnică asemănătoare este următoarea: „Se dă un dreptunghi de dimensiuni $7 x 10$. Din colţurile lui scoatem câte un pătrat de latură $1$. Să se arate că figura rămasă nu poate fi pardosită cu dreptunghiuri de laturi $3$ şi $1$.” Pentru probleme de acelaşi gen şi soluţia la această problemă puteţi să consultaţi în [1] secţiunea $1.1 Invariant$, sau în [2] secţiunea $Probleme de colorare şi acoperire$. Problema în care eliminăm două pătrate de aceiaşi culoare sau chiar cazul generalizat în care eliminăm un număr mai mare de pătrăţele o vom discuta în numărul viitor.

h2(#prob1ema5). Problema 5

h2(#problema5). Problema 5

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $2 x N$ cu dominouri.

p=. !probleme-de-acoperire-1?P51.jpg!

h2(#prob1ema6). Problema 6 ( _ONI 2001, clasa a X-a,_ [3] )

h2(#problema6). Problema 6 ( _ONI 2001, clasa a X-a,_ [3] )

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $3 x N$ cu dominouri.

Iar cum o matrice o putem ridica la o putere în număr logaritmic de paşi, putem afla <tex> X[n] </tex> mult mai repede.

h2(#prob1ema7). Problema 7 ( _ACM ICPC 1997_ )

h2(#problema7). Problema 7 ( _ACM ICPC 1997_ )

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $N x M (N <= 20, M <= 20)$ cu dominouri.

* Pentru cazul general $M x N$, presupunem fără a reduce generalizarea că $N$ e multiplu de $3$. Pentru $M <= 5$ problema e deja rezolvată. Să vedem acum rezolvarea pentru $M > 5$: dacă $M$ e par atunci putem obţine uşor o soluţie folosind dreptunghiuri de dimensiune $2 x 3$, iar dacă $M$ e impar atunci obţinem întâi o soluţie pentru $(M – 2) x N$ la care adăugăm o bandă de dimensiune $2 x N$ formată din dreptunghiuri $2 x 3$.

h2(#prob1ema9). Problema 9

h2(#problema9). Problema 9

bq. Pentru un dreptunghi de dimensiuni $N x M$ să se determine o acoperire cu dominouri a lui astfel încât să nu existe vreo linie verticală sau orizontală care să taie dreptunghiul în două fără să intersecteze vreun domino.