Fişierul intrare/ieşire:ppcover.in, ppcover.outSursăLot Vrancea 2010, Baraj 3
AutorMugurel Ionut AndreicaAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test3.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 [a1 ,b1], [a2 ,b2], [a3 ,b3] şi conţine în interiorul său toate celulele (i,j,k) cu a1≤i≤b1, a2≤j≤b2 şi a3≤k≤b3. Volumul paralelipipedului este (b1-a1+1)*(b2-a2+1)*(b3-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ă.

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 N2 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≤N2) 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 N2 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

ppcover.inppcover.out
2
2
11
00
10
01
3
001
100
101
011
000
000
000
011
100
5
22
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content