margi

În săptămâna Altfel - ”Să știi mai multe, să fii mai bun”, elevii $A$ și $B$ se joacă un joc altfel, joc numit „margi”. Cei doi au la dispoziție o matrice pătratică binară de dimensiune $2^n$.

Desfășurarea jocului este următoarea:

• jocul începe la nivelul $n$, când se împarte matricea inițială în $4$ matrici disjuncte de dimensiunea $2^{n-1}$;
• fiecare dintre cei doi jucători alege o matrice dintre cele $4$ și adună la punctajul său numărul de valori de $1$ conținut de matricea aleasă. Dacă ambii jucători aleg aceeași matrice doar jucătorul $A$ adună la punctajul său numărul de valori de $1$ din matrice;
• pentru fiecare nivel, după împărțirea matricei inițiale, matricele rezultate vor fi numerotate asemănător figurii alăturate;
• la nivelul $n - 1$ fiecare dintre matricele alese de jucători se împart în $4$ matrici disjuncte de dimensiunea $2^{n-2}$. Fiecare dintre cei doi jucători aleg o matrice din cele noi formate.
• pentru fiecare nivel jucat fiecare jucător trebuie să aleagă o matrice;
• jocul continua cu nivelele $n-2$, $n-3$, etc;
• jocul se termină când dimensiunea matricelor alese este $1$;

Scopul jocului este obținerea sumei maxim posibile prin adunarea punctajelor celor doi jucători. Dacă există mai multe posibilități de obținere a acestei sume, fiecare jucător va alege matricele cu număr de ordine mai mic. Exemplu: pentru $n=3$, vom simula un joc:

• Jucătorul $A$

Alege matricea ce are colțul stânga-sus în ($1, 1$), numerotat cu $1$. Punctaj $Sum_A = 7$.

• Jucătorul $B$

Alege matricea ce are colțul stânga-sus în ($5, 1$), numerotat cu $3$. Punctaj $Sum_B = 5$.

• Jucătorul $A$

Alege matricea ce are colțul stânga-sus în ($1, 1$), numerotat cu $1$. Punctaj $Sum_A = 7 + 3 = 10$

• Jucătorul $B$

Alege matricea ce are colțul stânga-sus în ($7, 1$), numerotat cu $3$. Punctaj $Sum_B = 5 + 3 = 8$

• Jucătorul $A$

Alege matricea ce are colțul stânga-sus în ($1, 2$), numerotat cu $2$. Punctaj $Sum_A = 10 + 1 = 11$.
Jucătorul $A$ a obținut $Sum_A = 11$, secvența alegerilor efectuate fiind: $1$, $1$, $2$.

• Jucătorul $B$

Alege matricea ce are colțul stânga-sus în ($7, 2$), numerotat cu $2$. Punctaj $Sum_B = 8 + 1 = 9$

Jucătorul $B$ a obținut $Sum_B = 9$, secvența alegerilor efectuate fiind: $3$, $3$, $2$.

Cerinţă

Pentru un $n$ număr natural dat și o matrice binară de dimensiunea $2^n$, se cere să se determine punctajul maxim obținut de cei doi jucători. Se cere și determinarea unei strategii de alegere a matricelor la fiecare pas care să ducă la obținerea punctajului maxim.

Date de intrare

Fişierul de intrare margi.in conţine pe prima linie un număr natural $C$. Pe linia a doua se află un număr natural $n$. Pe următoarele $2^n$ linii, elementele matricei binare.

Date de ieșire

Fişierul de ieșire margi.out conţine pe prima linie suma maximă care se poate obține prin însumarea punctajelor celor doi jucători. În cazul în care $C = 1$ în fișierul de ieșire va apărea doar această valoare. Dacă $C = 2$ fișierul de ieșire va conține, în continuare:

Pe cea de-a doua linie se vor scrie $n$ numere ce reprezintă secvența de matrici alese de jucătorul $A$.
Pe cea de-a treia linie se vor scrie $n$ numere ce reprezintă secvența de matrici alese de jucătorul $B$.
Secvențele de matrici alese de cei doi trebuie să respecte următoarele două condiții:

1. suma celor două punctaje obținute de cei doi jucători este maximă. Pot exista mai multe secvențe de matrici care au suma maximă.
2. Fie $A_n$, $A_{n-1}$, $\dots$, $A_1$ secvențele de matrici alese de $A$, respectiv $B_n$, $B_{n-1}$, $\dots$, $B_1$, secvențele de matrici alese de $B$, la nivelele $n$, $n-1$, $\dots$, $2$, $1$. Dacă compunem șirul $A_n$, $B_n$, $A_{n-1}$, $B_{n-1}$, $A_{n-2}$, $B_{n-2}$, $\dots$, $A_1$, $B_1$, dintre toate șirurile posibile care dau suma maximă, trebuie ales cel șirul minim lexicografic.

Restricții și precizări

• $C$ poate fi $1$ sau $2$
• $2 \leq n \leq 10$
• Spunem că șirul $X$ este mai mic lexicografic decât șirul $Y$, dacă există o poziție $i$, astfel încât $X_1$ = $Y_1$, $X_2$ = $Y_2$, $\dots$, $X_{i-1}$ = $Y_{i-1}$, iar $X_i$ < $Y_i$.
• Pentru teste în valoare de $30$ de puncte avem $C = 1$.

Exemplul 1

margi.in

1
2
0000
0100
0000
0000

margi.out

2

Explicație

Suma maximă = ($0$ + $1$) + ($0$ + $1$) = $2$. Dacă am fi avut $C = 2$, pe liniile $2$ și $3$ ar mai fi apărut:

1 1
1 4

Exemplul 2

margi.in

2
3
01001100
11100011
00101000
11000000
00000000
01100100
01000000
11000010

margi.out

20
1 1 2
3 3 2

Explicație

Suma maximă = ($7 + 5$) + ($3 + 3$) + ($1 + 1$) = $20$. Exemplul din figura de mai sus.