De exemplu, pentru $n = 10, k = 4$ şi matricea
!problema/radioactiv?x.PNG!
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$
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 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$
h2. Cerinţă
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$.
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!
h2. Cerinţă
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") ==
