joc15

Joc15

== include(page="template/taskheader" task_id="joc15") ==

p<>. Atunci când este plictisit, Costel inventează jocuri logice şi încearcă să le rezolve. Într-o zi Costel ia o tablă dreptunghiulară împărţită în $M x N$ pătrăţele identice, asemănătoare unei table de şah, şi aşează pe aceasta cuburi identice astfel încât, pe fiecare pătrat al tablei să se afle cel puţin un cub şi cel mult $10$ cuburi suprapuse. Costel determină  numărul minim de cuburi aşezate pe o poziţie a tablei, notat cu $MIN$.

p<>. Atunci când este plictisit, Costel inventează jocuri logice şi încearcă să le rezolve. Într-o zi Costel ia o tablă dreptunghiulară împărţită în $M x N$ pătrăţele identice, asemănătoare unei table de şah, şi aşează pe aceasta cuburi identice astfel încât, pe fiecare pătrat al tablei să se afle cel puţin un cub şi cel mult $10$ cuburi suprapuse. Costel determină numărul minim de cuburi aşezate pe o poziţie a tablei, notat cu $MIN$.

p<>. El defineşte noţiunea de mutare astfel: alege patru pătrăţele învecinate, care formează un pătrat compus din $2 x 2$ pătrăţele şi ridică toate cuburile de pe aceste poziţii astfel ca, pe fiecare dintre cele patru pătrăţele, să existe un număr de cuburi egal cu $MIN$. Efortul necesar efectuării mutării este egal cu $MAX - MIN$, unde $MAX$ reprezintă numărul maxim de cuburi aflat pe unul dintre cele patru pătrăţele alese.

h2. Cerinţă

Determinaţi o modalitate de a acoperi suprafaţa în întregime cu piese de arie $4$ unităţi care au forma următoare:
!problema/acoperire?a.png!
 
Piesele pot fi si rotite sau întoarse putând astfel să folosim toate cele $8$ moduri de a le aşeza.

Determinaţi valoarea efortului total minim depus pentru rezolvarea jocului.

h2. Date de intrare

Fişierul $acoperire.in$ conţine pe prima linie un număr natural $N$, cu semnificaţia din enunţ.

Fişierul $joc15.in$ are următoarea structură:
 
* pe prima linie se află două numere naturale $M$ şi $N$, separate printr-un singur spaţiu, reprezntând numărul liniilor, respectiv numărul coloanelor tablei de joc.
* Pe următoarele $M$ linii se află câte $N$ numere naturale, separate prin câte un spaţiu, reprezentând numărul iniţial de cuburi aflate pe fiecare pătrăţel al tablei de joc.

h2. Date de ieşire

Fişierul $acoperire.out$ va conţine valoarea $-1$ pe prima linie dacă problema nu are soluţie, iar în caz contrar va avea următoarea structură: $N$ linii cu câte $N$ valori fiecare reprezentând codificarea suprafeţei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu. Poziţiile ocupate de prima piesă aşezată se vor codifica cu $1$, poziţiile ocupate de a doua piesă aşezată se vor codifica cu $2$ etc. Corespunzător colţurilor lipsă se va scrie valoarea $0$.

Fişierul $joc15.out$ va conţine un singur număr natural reprezentând valoarea efortului total minim.

h2. Restricţii

* $6 ≤ N ≤ 20$
* Piesele trebuie să fie complet în interiorul zonei
* Zona trebuie acoperită integral
* Două piese nu se pot suprapune complet sau parţial

* $M$ şi $N$ sunt numere naturale mai mari sau egale cu $2$ cu proprietatea că $4 ≤ M x N ≤ 18$
* Numărul cuburilor plasate pe o poziţie a tablei este un număr natural între $1$ şi $10$

h2. Exemplu

table(example). |_. acoperire.in |_. acoperire.out |
| 6
| 0 7 2 2 2 0
3 7 2 4 4 4
3 7 7 4 5 5
3 3 6 1 1 5
6 6 6 8 1 5
0 8 8 8 1 0
|

table(example). |_. joc15.in |_. joc15.out |_. Explicaţie |
| 3 4
2 3 2 2
2 4 3 2
3 2 4 2
| 4
| Minimul este $2$. O succesiune optimă de mutări poate fi:
Mutarea $1:$ Se aleg poziţiile $(2, 2), (2, 3), (3, 2)$ şi $(3, 3)$ Efortul este $4 – 2 = 2$
Mutarea $2:$ Se aleg poziţiile $(1, 1), (1, 2), (2, 1)$ şi $(2, 2)$ Efortul este $3 – 2 = 1$
Mutarea $3:$ Se aleg poziţiile $(2, 1), (2, 2), (3, 1)$ şi $(3, 2)$ Efortul este $3 – 2 = 1$
Efortul total este $4$.
|
 

== include(page="template/taskfooter" task_id="joc15") ==

5815