== include(page="template/taskheader" task_id="pixels") ==
Vi se dă o matrice de $N * N$ pixeli. Datoria voastră este să coloraţi fiecare pixel în alb sau negru astfel încât plăcerea vizuala să fie cât mai mare. Pentru a face asta trebuie să 3 reguli. În primul rând, pentru fiecare pixel ştiţi cantitatea de plăcere Aij pe care o provoacă dacă este colorat în alb. În al doilea rând, pentru fiecare pixel ştiţi cantitatea de plăcere Bij pe care o provoacă dacă este colorat în negru. În al treilea rând, ştiţi pentru fiecare pereche de pixeli adiacenţi (adică au o muchie în comun) care este costul plăcerii Cijk care trebuie plătit dacă sunt coloraţi diferit.
Costul plăcerii este dat pentru fiecare pixel şi pentru fiecare 4 direcţii. Cu alte cuvinte, pentru un anumit pixel la coordonate (i, j), Cij0 este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele (i - 1, j) sunt coloraţi diferit, Cij1 este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele (i, j + 1) sunt coloraţi diferit, Cij2 este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele (i + 1, j) sunt coloraţi diferit, şi Cij3 este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele (i, j - ) sunt coloraţi diferit.
Dacă un pixel nu are un vecin valid (adică unul care să facă parte din matrice), costul tot va fi dat, dar va fi 0. De exemplu C110 va fi întotdeauna 0.
Cij0 şi C(i-1)j2 vor fi întotdeauna la fel şi aşa mai departe (costul pentru fiecare pereche este simetric).
Voi trebuie să maximizaţi plăcerea totală, adică: * suma Aij pentru toţi pixelii coloraţi în alb + suma Bij pentru toţi pixelii coloraţi în negru - suma costurilor pixelilor adiacenţi coloraţi diferit*. Fiecare pereche de pixeli adiacenţi coloraţi diferit contribuie o singura dată (nu de două ori) la costul total pentru pixelii adiacenţi coloraţi diferit.
Vi se dă o matrice de $N * N$ pixeli. Datoria voastră este să coloraţi fiecare pixel în alb sau negru astfel încât plăcerea vizuală să fie cât mai mare. Pentru a face asta trebuie să ştiţi 3 reguli. În primul rând, pentru fiecare pixel ştiţi cantitatea de plăcere $A{~ij~}$ pe care o provoacă dacă este colorat în alb. În al doilea rând, pentru fiecare pixel ştiţi cantitatea de plăcere $B{~ij~}$ pe care o provoacă dacă este colorat în negru. În al treilea rând, ştiţi pentru fiecare pereche de pixeli adiacenţi (adică au o muchie în comun) care este costul plăcerii $C{~ijk~}$ care trebuie *plătit* dacă sunt coloraţi diferit.
Costul plăcerii este dat pentru fiecare pixel şi pentru fiecare 4 direcţii. Cu alte cuvinte, pentru un anumit pixel la coordonate $(i, j)$, $C{~ij0~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i - 1, j)$ sunt coloraţi diferit, $C{~ij1~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i, j + 1)$ sunt coloraţi diferit, $C{~ij2~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i + 1, j)$ sunt coloraţi diferit, şi $C{~ij3~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i, j - 1)$ sunt coloraţi diferit.
Dacă un pixel nu are un vecin valid (adică unul care să facă parte din matrice), costul tot va fi dat, dar va fi 0. De exemplu $C{~110~}$ va fi întotdeauna 0. $C{~ij0~}$ şi $C{~i-1j2~}$ vor fi întotdeauna la fel, şi aşa mai departe (costul pentru fiecare pereche este simetric).
Voi trebuie să maximizaţi plăcerea totală, adică: *suma $A{~ij~}$ pentru toţi pixelii coloraţi în alb + suma $B{~ij~}$ pentru toţi pixelii coloraţi în negru - suma costurilor pixelilor adiacenţi coloraţi diferit*. Fiecare pereche de pixeli adiacenţi coloraţi diferit contribuie o singura dată (nu de două ori) la costul total pentru pixelii adiacenţi coloraţi diferit.
Baftă!
h2. Date de intrare
Fişierul de intrare $pixels.in$ conţine pe prima linie $N$, dimensiunea matricii. Apoi urmează $N$ linii cu $N$ valori pe fiecare din ele. Cea de-a $j$-a valoare de pe linia $i$ reprezintă Aij. În acelaşi format urmează $N$ linii cu $N$ valori reprezentând Bij. La final, $N * N$ linii
Fişierul de intrare $pixels.in$ conţine pe prima linie $N$, dimensiunea matricii. Apoi urmează $N$ linii cu $N$ valori pe fiecare din ele. Cea de-a $j$-a valoare de pe linia $i$ reprezintă $A{~ij~}$. În acelaşi format urmează $N$ linii cu $N$ valori reprezentând $B{~ij~}$. La final sunt $N * N$ linii cu câte 4 valori pe fiecare linie. Cea de-a $(i - 1) * N + j$ - a linie din acest grup conţine $C{~ij0~}$ $C{~ij1~}$ $C{~ij2~}$ $C{~ij3~}$.
h2. Date de ieşire
În fişierul de ieşire $pixels.out$ ...
În fişierul de ieşire $pixels.out$ trebuie să afişaţi o singură linie care reprezintă plăcerea maximă care poate fi obţinută.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100$
* $1 ≤ A{~ij~}, B{~ij~}, C{~ijk~} ≤ 100$
* 10% din teste vor avea $N = 4$
* 30% din teste vor acea $N = 10$
h2. Exemplu
table(example). |_. pixels.in |_. pixels.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
1 10
2 2
10 1
3 3
0 1 1 0
0 0 1 1
1 53 0 0
1 0 0 53
| 24
|
h3. Explicaţie
...
Plăcerea maximă se obţine colorând
Negru Alb
Negru Negru
Observaţi că pixelii $(2, 1)$ şi $(2, 2)$ au un cost foarte mare de a fi colorţi diferit, aşa că îi veţi colora le fel, negru fiind opţiunea cea mai bună.
== include(page="template/taskfooter" task_id="pixels") ==
