== include(page="template/taskheader" task_id="ppcover") ==
Poveste şi cerinţă...
Să considerăm un cub de latură $N$, compus din $NxNxN$ celule. O celulă $(i,j,k)$ $(0≤i,j,k≤N-1)$ conţine o valoare $C(i,j,k)$ care poate fi ori $0$, ori $1$. Dorim să amplasăm în interiorul cubului două paralelipipede, astfel încât fiecare celulă $(i,j,k)$ cu $C(i,j,k)=1$ să se afle în interiorul cel puţin unui paralelipiped. Cele două paralelipipede se pot intersecta.
Un paralelipiped este definit de $3$ intervale $[a{~1~} ,b{~1~}]$, $[a{~2~} ,b{~2~}]$, $[a{~3~} ,b{~3~}]$ şi conţine în interiorul său toate celulele $(i,j,k)$ cu $a{~1~}≤i≤b{~1~}$, $a{~2~}≤j≤b{~2~}$ şi $a{~3~}≤k≤b{~3~}$. Volumul paralelipipedului este $(b{~1~}-a{~1~}+1)*(b{~2~}-a{~2~}+1)*(b{~3~}-a {~3~}+1)$.
Determinaţi o amplasare a două paralelipipede care să respecte condiţiile specificate, astfel încât suma volumelor celor două paralelipipede să fie minimă.
h2. Date de intrare
Fişierul de intrare $ppcover.in$ ...
Prima linie a fişierului de intrare $ppcover.in$ conţine numărul $T$ de teste descrise în continuare. Prima linie a fiecărui test conţine numărul $N$, reprezentând dimensiunea laturii cubului. Următoarele $N^2^$ linii conţin câte $N$ caractere fiecare (plus caracterul de linie nouă la sfârşitul fiecărei linii). A $L$-a astfel de linie $(1≤L≤N^2^)$ corespunde celulelor $(i,j,k)$ pentru care $i=(L-1) div N$ şi $j=(L-1) mod N$. Al k-lea caracter $(1≤k≤N)$ de pe a $L$-a linie dintre cele $N^2^$ corespunde valorii $C(i,j,k-1)$; dacă acest caracter este $‘0’$ atunci $C(i,j,k-1)=0$ şi dacă acest caracter este $‘1’$ atunci $C(i,j,k-1)=1$.
h2. Date de ieşire
În fişierul de ieşire $ppcover.out$ ...
În fişierul de ieşire $ppcover.out$ veţi afişa câte o linie pentru fiecare test dat în fişierul de intrare, conţinând suma minimă a volumelor celor două paralelipipede.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 40$
* $1 ≤ N ≤ 40$
* Este permis ca paralelipipedele (unul dintre ele sau ambele) să aibă volumul $0$.
h2. Exemplu
table(example). |_. ppcover.in |_. ppcover.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
2
11
00
10
01
3
001
100
101
011
000
000
000
011
100
| 5
22
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="ppcover") ==
