Fişierul intrare/ieşire:	ppcover.in, ppcover.out	Sursă	Lot Vrancea 2010, Baraj 3
Autor	Mugurel Ionut Andreica	Adăugată de	Andrei Misarca •Mishu91
Timp execuţie pe test	1.575 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ppcover

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₁ ,b₁], [a₂ ,b₂], [a₃ ,b₃] şi conţine în interiorul său toate celulele (i,j,k) cu a₁≤i≤b₁, a₂≤j≤b₂ şi a₃≤k≤b₃. Volumul paralelipipedului este (b₁-a₁+1)*(b₂-a₂+1)*(b₃-a ₃+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ă.

Date de intrare

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² 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²) 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² 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.

Date de ieşire

Î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.

Restricţii

• 1 ≤ T ≤ 40
• 1 ≤ N ≤ 40
• Este permis ca paralelipipedele (unul dintre ele sau ambele) să aibă volumul 0.

Exemplu

Cum se trimit solutii?