(Categoria _Algoritmi_, autor _Cosmin Negruşeri_)
(toc){width: 33em}*{text-align:left} *Cuprins:*

* 'Problema 1 ( _MagicBoxes, TopCoder_ ) ':probleme-de-acoperire2#prob1
* 'Problema 2 ( _IOI 2001 Pavement, problemă de rezervă_, [1] ) ':probleme-de-acoperire2#prob2

* 'Problema 1 ( _MagicBoxes_ ) ':probleme-de-acoperire2#prob1
* 'Problema 2 ( _IOI 2001 Pavement_, [1] ) ':probleme-de-acoperire2#prob2

* 'Problema 3 ( _ACM ICPC 1997_ ) ':probleme-de-acoperire2#prob3

* 'Problema 4 ( _Hardwood Floor, acm.sgu.ru_ ) ':probleme-de-acoperire2#prob4

* 'Problema 4 ( _Hardwood Floor_ ) ':probleme-de-acoperire2#prob4

* 'Problema 5 ( _TopCoder, CaseysArt_ ) ':probleme-de-acoperire2#prob5

* 'Problema 6 ( _Another chocolate maniac, acm.sgu.ru_ ) ':probleme-de-acoperire2#prob6

* 'Problema 6 ( _Another chocolate maniac_ ) ':probleme-de-acoperire2#prob6

* 'Problema 7 ( _Bugs, CEOI 2002_, [2] ) ':probleme-de-acoperire2#prob7

* 'Problema 8 ( _CSP 1993, Lot 2001, Dominoes acm.sgu.ru, IPSC 2004 sample task, Algoritmus 2005, IOI 2005 practice task_ ) ':probleme-de-acoperire2#prob8

* 'Problema 8 ( _CSP 1993, Lot 2001, Domino, IPSC 2004, Algoritmus 2005, IOI 2005_ ) ':probleme-de-acoperire2#prob8

* 'Aplicaţii':probleme-de-acoperire2#app
* 'Bibliografie':probleme-de-acoperire2#biblio

Această reprezentare pe biţi este foarte utilă în probleme de acest gen, şi cum avem întregi de $64$ de biţi pe care îi putem folosi, avem o metodă foarte simplă de reprezentare a tablelor de mărime până la $64$.

h2(#prob2). Problema 2 ( _IOI 2001 Pavement, problemă de rezervă_ )

h2(#prob2). Problema 2 ( _IOI 2001 Pavement_ )

bq. Se dă o matrice de dimensiuni $N x M (1 <= N <= 7 şi 1 <= M <= 100)$. Unele celule ale acestei matrici sunt distruse şi trebuie acoperite cu piese de forma din $Fig. 1$. Fiecare celulă rămasă neacoperită se consideră o greşeală, iar dacă o piesă cu care am acoperit celule distruse a trebuit să fie tăiată pentru a acoperi numai celule distruse, fiecare pătrăţel din partea nefolosită a piesei este considerată o greşeală. Se cere acoperirea tablei astfel ca numărul de greşeli să fie minimizat. În $Fig. 2$, pentru prima tablă, acoperirea optimă are două greşeli, aşa cum vedem în al doilea desen.

Tablei îi adăugăm la sfârşit o coloană pe care nu pot fi aşezate piese. Rezultatul cerut de problemă se va afla în $max[N][M + 1][0]$. Menţionăm că $Problemele 2, 3$ şi $4$ pot fi rezolvate în mod asemănător în complexitate $O(N * M * 2^M^)$.

h2(#prob8). Problema 8 ( _CSP 1993, Lot 2001, "Domino":http://acm.sgu.ru/problem.php?contest=0&problem=101, "The Tiling Problem":http://ipsc.ksp.sk/contests/ipsc2004/practice/problems/t.php, Algoritmus 2005, IOI 2005 practice task_ )

h2(#prob8). Problema 8 ( _CSP 1993, Lot 2001, "Domino":http://acm.sgu.ru/problem.php?contest=0&problem=101, "The Tiling Problem":http://ipsc.ksp.sk/contests/ipsc2004/practice/problems/t.php, Algoritmus 2005, IOI 2005_ )

bq. Se dă o tablă de dimensiuni $N x M$, din care unele pătrate sunt eliminate. Se cere să se determine o acoperire a tablei cu număr maxim de dominouri $(1 <= N, M <= 200)$. De exemplu, o tablă ce nu are nicio celulă eliminată, de $3 x 3$ pătrăţele poate fi acoperită cu cel mult $4$ dominouri care nu se suprapun. O soluţie posibilă este prezentată în a doua figură.

h2(#app). Aplicaţii

* "Pavare":http://infoarena.ro/problema/pavare
* "Little Kings":http://acm.sgu.ru/problem.php?contest=0&problem=223

* "Pavare":http://infoarena.ro/problema/pavare, infoArena
* "Little Kings":http://acm.sgu.ru/problem.php?contest=0&problem=223, SGU

h2(#biblio). Bibliografie