Cod sursa(job #3352550)

Utilizator mariusn01Marius Nicoli mariusn01 Data 28 aprilie 2026 18:21:54
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
/// 2 la (una dintre dimensiuni) * n * m

/**
- Observatia 1:
A da flip de doua ori la o linie (sau o coloana) e ca si cum nu as da deloc
Decim la orice linie si la orice coloana am 2 variante: sa ii dau flip (o data) sau sa nu ii dau.

- Observatia 2: cat de mare este matricea data ?

Generez toate variantele de a flipui coloane.

 0  0  0
 -------
 4 -2  2
 3 -1  5
 2  0 -3
 4  1 -3
 5 -3  2

 0  0  1
 -------
 4 -2 -2
 3 -1 -5
 2  0 +3
 4  1 +3
 5 -3 -2

 0  1  0
 -------
 4 +2  2
 3 +1  5
 2  0 -3
 4 -1 -3
 5 +3  2

 0  1  1
 -------
 4 +2 -2
 3 +1 -5
 2  0 +3
 4 -1 +3
 5 +3 -2

 ...

 1  1  1
 -------
-4 +2 -2
-3 +1 -5
-2  0 +3
-4 -1 +3
-5 +3 -2

**/

#include <fstream>
using namespace std;

int a[16][16], x[16][16];
int n, m, i, j, k;
int sumaLinie, sumaMatrice, sol;
int main () {
    ifstream fin ("flip.in");
    ofstream fout("flip.out");
    fin>>n>>m;
    for (i=0;i<n;i++)
        for (j=0;j<m;j++)
            fin>>a[i][j];
    sol = -1;
    for (k=0;k<(1<<m);k++) {
        /// flipuiesc coloanele conform bitilor de 1 din scrierea in baza 2 a lui k

        for (i=0;i<n;i++)
            for (j=0;j<m;j++)
                x[i][j] = a[i][j];

        for (int b=0;b<m;b++)
            if ((k>>b) & 1) {
                /// flipuiesc coloana b a matricei
                for (i=0;i<n;i++)
                    x[i][b] = -x[i][b];
            }
        /// aici ajung sa am matricele x dupa un anume mod de a aplica o flipuire pe coloane
        /// imi pun problema, pentru aceasta flipuire pe coloane, ce pot face cu liniile ?
        /// liniile cu suma pozitiva le las asa iar pe cele cu suma negativa le flipuiesc

        sumaMatrice = 0;
        for (i=0;i<n;i++) {
            sumaLinie = 0;
            for (j=0;j<m;j++)
                sumaLinie += x[i][j];
            if (sumaLinie > 0)
                sumaMatrice += sumaLinie;
            else
                sumaMatrice -= sumaLinie;
        }

        if (sumaMatrice > sol)
            sol = sumaMatrice;
/**
        for (i=0;i<n;i++) {
            for (j=0;j<m;j++)
                fout<<x[i][j]<<" ";
            fout<<"\n";
        }
        fout<<"\n";
**/
    }
    fout<<sol;

    return 0;
}