Lista de probleme 2

Filtrare

#4013 CMGB

Cunoscutul programator Văndămel are la dispoziție o matrice binară cu n linii (numerotate de la 1 la n) și m coloane (numerotate de la 1 la m). Văndămel poate efectua, de câte ori e posibil, următoarea operație: alege două poziții vecine pe linie sau pe coloană și care conțin ambele valoarea 1 și le transformă în 0. Văndămel știe să rezolve orice problemă cu matrice, dar vrea să vadă dacă știți și voi să aflați numărul maxim posibil de operații care se pot efectua pe matricea dată.

Se dă un șir a0, a1, …, an-1 de numere naturale nenule. Trebuie să rearanjați elementele șirului astfel încât pe orice poziție i (i=0..n-1) să se afle un număr care are în baza 2 bitul i setat la 1.