== include(page="template/taskheader" task_id="joc8") ==
Poveste și cerință...
Fie o matrice lidoriană de $x$ linii și $y$ coloane. Liniile matricei se numerotează de jos în sus, cu numere de la $0$ la $x-1$. Coloanele matricei se numerotează de la dreapta la stânga, cu numere de la $0$ la $y-1$. Matricea lidoriană este formată doar din valori $1$ și [$0$].
!problema/joc8?fig1.jpg!
Pentru fiecare linie [$i$], se calculează $sli$ ca suma tuturor produselor dintre $a(i,j)$ și [$2j$]. Pentru fiecare coloană [$k$], se calculează $sck$ ca suma tuturor produselor dintre $a(i,k)$ și $2i .
!problema/joc8?fig2.jpg!
Fie $S1$ suma tuturor sumelor calculate pe linii și fie $S2$ suma tuturor sumelor calculate pe coloane.
$S1$ $=$ $Sl0$ $+$ $Sl1$ $+$ $Sl2$ $S2$ $=$ $Sc0$ $+$ $Sc1$ $+$ $Sc2$ $+$ $Sc3$
Considerăm $t=S1+S2$. Se înțelege prin „mutare” o interschimbare între oricare două valori $1$ și $0$ din matrice.
Jocul lidorian presupune executarea unui număr minim de mutări, astfel încât valoarea lui $t$ să fie minimă.
h2. Cerință
Să se scrie un program care să permită calcularea valorii minime a lui [$t$]. Pentru această valoare a lui [$t$], se cere să se determine numărul minim de mutări necesare.
h2. Date de intrare
Fișierul de intrare $joc8.in$ ...
Fișierul de intrare $joc8.in$ conține în ordine, pe linii:
$x$ $y$ număr de linii,număr de coloane despărțite printr-un spațiu
$ax-1,y-1$ $ax-1,y-2$ ... $ax-1,0$ elementele liniei $x-1$, fără spații între ele
$ax-2,y-1$ $ax-2,y-2$ ... $ax-2,0$ elementele liniei $x-2$, fără spații între ele
...
$a0,y-1$ $a0,y-2$ ... $a0,0$ elementele liniei [$0$], fără spații între ele
h2. Date de ieșire
În fișierul de ieșire $joc8.out$ ...
Fișierul de ieșire $joc8.out$ conține, în ordine, pe prima linie, valoarea [$t$], apoi numărul minim de mutări, cu un singur spațiu între ele.
h2. Restricții
* $... ≤ ... ≤ ...$
* $2$ ≤ [$x$], $y$ ≤ $12$
* Matricea conține cel puțin o cifră de $1$
h2. Exemplu
table(example).
|_. joc8.in |_. joc8.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|_. joc8.in |_. joc8.out |_. Explicatie |
| 5 6
100010
010000
000001
000010
011000
| 28 5
| !problema/joc8?fig3.jpg!
|
h3. Explicație
