Probleme de acoperire

(Categoria Algoritmi, autor Cosmin Negruşeri)

În acest articol vom prezenta o serie de probleme apărute la concursurile de programare care au o tematică similară şi anume acea de acoperire în plan. În general acest tip de probleme sunt NP complete, dar pentru cazurile particulare prezentate problemele sunt rezolvabile.

Problema 1 (Olimpiada de informatică, Bucureşti, etapa pe sector, 1995 şi [1])

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:

Soluţie: