== include(page="template/taskheader" task_id="joc8") ==
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ă $sl[~i~]$ ca suma tuturor produselor dintre $a(i,j)$ și $2[^j^]$. Pentru fiecare coloană [$k$], se calculează $sc[~k~]$ ca suma tuturor produselor dintre $a(i,k)$ și $2[^i^]$ .
!problema/joc8?fig2.jpg!
Fie $S1$ suma tuturor sumelor calculate pe linii și fie $S2$ suma tuturor sumelor calculate pe coloane.
$S[~1~]$ = $Sl[~0~]$ + $Sl[~1~]$ + $Sl[~2~]$ $S[~2~]$ = $Sc[~0~]$ + $Sc[~1~]$ + $Sc[~2~]$ + $Sc[~3~]$
Considerăm $t=S[~1~]+S[~2~]$. 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.
Poveste și cerință...
h2. Date de intrare
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
$a[~x-1,y-1~]$ $a[~x-1,y-2~]$ ... $a[~x-1,0~]$ elementele liniei $x-1$, fără spații între ele
$a[~x-2,y-1~]$ $a[~x-2,y-2~]$ ... $a[~x-2,0~]$ elementele liniei $x-2$, fără spații între ele
...
$a[~0,y-1~]$ $a[~0,y-2~]$ ... $a[~0,0~]$ elementele liniei [$0$], fără spații între ele
Fișierul de intrare $joc8.in$ ...
h2. Date de ieșire
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.
În fișierul de ieșire $joc8.out$ ...
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 |
| 5 6
100010
010000
000001
000010
011000
| 28 5
|
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
!problema/joc8?fig.jpg!
...
== include(page="template/taskfooter" task_id="joc8") ==
