radioactiv

Radioactiv

p<>. Factorul radioactiv al celulei de pe linia $5$ şi coloana $5$ se calculează cu ajutorul sumelor valorilor din celulele marcate prin culori: $2*1+(0+1-1+1+0+2+0+1)*(1-1/4)+(0+1+0-1-2-1-3-1+ 0+1+0+0+0+1+0+0)*(1-2/4)+(1+0+2+1+2+0+0+0+0-1+0+2+1-5+0+3+0-1-2+2+0+0+1+1)*(1-3/4) = 2+3-5/2+7/4 = 4.25$

p<>. Factorul celulei de pe linia $10$ şi coloana $2$ este: $1*(-1)+(-1)*(1-1/4)+4*(1-2/4)+0*(1-3/4) = -1+3/4+2+0 = 1.75$.
 

p<>. Factorul celulei de pe linia $10$ şi coloana $2$ este: $1*(-1)+(-1)*(1-1/4)+4*(1-2/4)+0*(1-3/4) = -1-3/4+2+0 = 0.25$.

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.

Să se determine numărul de celule ale matricei în care factorul radioactiv este minim.

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 $radioactiv.in$ are pe prima linie valorile naturale $n$ şi $k$, iar pe următoarele $n$ linii câte $n$ valori întregi, despărţite prin câte un spaţiu, reprezentând valorile din matrice.

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 $radioactiv.out$ va conţine un singur număr natural reprezentând numărul de celule ale matricei în care factorul radioactiv este 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

* $1 ≤ n ≤ 500$
* $1 ≤ k ≤ 20$
* valorile din matrice sunt numere întregi cu cel mult $2$ cifre
 

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). |_. radioactiv.in |_. radioactiv.out |_. Explicaţii |
| 10 4
+1  +2  -1 -3  +4  +1  +1  +1  +1 +1
+0  +1  +2  +0  +0  +0  +0 -1  +1  +0
+3  +2  +0 -1 -2 %{color:blue}**-1**% -3  +0  +1  +2
+1  +0  +1  +0  +1 %{color:blue}**-1**% -1  +2  +0  +0
+0  +1  +0  +1  +2  +1  +0  +1  +0  +1
+2  +1  +0  +0  +2  +0  +1 -5  +0  +0
+0  +1  +0  +1  +0  +0  +0  +0  +2  +1
+1  +0  +0  +2 -2 -1  +0  +3  +1  +2
+0  +0  +0  +0  +1  +1  +1  +1  +1  +1
-1 -1  +0  +1 -1  +2 -1  +3  +0  +2
| 2
| Factorul radioactiv de valoare minimă $(-0.25)$ se obţine în celulele marcate.
|

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

5818