Cod sursa(job #3003631)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 15 martie 2023 20:31:42
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
/*
Generam toate posibilitatile de flip pentru coloane:
1. Ele sunt siruri de 0 si 1 de lungime m <=> 
Un numar in baza 2 cu m biti <=> Un numar in baza 10
m = 3

000 => 0
001 => 1
010 => 2
011 => 3
100 => 4
101 => 5
110 => 6
111 => 7

Operatii pe biti:
    // 1. << (shift left): (0101 << 1) = 01010 | (x << k) <=> (2^k) * x
    // 2. & (AND): 100101001 &
    //             110011000 =
    //             100001000
    // Cum stim daca bitul p al numarului x (in baza 10) este 1 sau 0?
    //               x = 101101001 &
    // p = 3 => (1<<p) = 000001000
    //                   000001000 > 0 ?
    // ((1<<p) & x) > 0 => DA
    // 3. | (OR): 100101001 |
    //            110011000 =
    //            110111001
    // 4. ^ (XOR): 100101001 |
    //             110011000 =
    //             010110001
    // 5. >> (shift right) => 1010110101 >> 4 = 0000101011
    // x >> k => x / (2^k) (fara rest)
*/
#include <fstream>
#include <vector>
#include <climits>

using namespace std;

vector<int> coloane;
int n, m, a[20][20], sol = -INT_MAX;

ifstream fin("flip.in");
ofstream fout("flip.out");

void flip_col(int col) {
    for(int lin = 1; lin <= n; lin++) {
        a[lin][col] *= -1;
    }
}

int main() {
    fin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            fin >> a[i][j];
        }
    }
    for(int mask = 0; mask < (1 << m); mask++) { // 1 << m = 2^m
        // mask e numar in baza 10
        // trebuie sa il traducem in baza 2 ca sa aflam subsetul de coloane flipuite
        for(int bit = 0; bit < m; bit++) {
            if(((1<<bit)&mask) > 0) {
                // Bitul bit e 1 => Coloana (bit + 1) va fi flipuita
                flip_col(bit + 1);
            }
        }
        int total = 0;
        for(int lin = 1; lin <= n; lin++) {
            int sum = 0;
            for(int j = 1; j <= m; j++) {
                sum += a[lin][j];
            }
            total += abs(sum);
        }
        sol = max(sol, total);
        // Undo
        for(int bit = 0; bit < m; bit++) {
            if(((1<<bit)&mask) > 0) {
                // Bitul bit e 1 => Coloana (bit + 1) va fi flipuita
                flip_col(bit + 1);
            }
        }
    } 
    fout << sol << "\n";
    return 0;
}