Cod sursa(job #119252)

Utilizator stefysStefan stefys Data 30 decembrie 2007 03:39:03
Problema Jocul Flip Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <stdio.h>
#include <math.h>
#include <string.h>

const unsigned int pow2[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,
                            8192,16384,32768,65536};

#define MAX_MAT_SIZE 16

long long Sum (long mat[][MAX_MAT_SIZE], unsigned int size_l, unsigned int size_c)
{
    long long S=0;
    unsigned int lin,col;
    for (col=0; col<size_c; col++)
        for (lin=0; lin<size_l; lin++)
            S += mat[lin][col];
    return S;
}


int main (void)
{
    unsigned int bin,lin,col;
    int N,M;
    long mat[MAX_MAT_SIZE][MAX_MAT_SIZE],mat2[MAX_MAT_SIZE][MAX_MAT_SIZE];
    long long S,S_max,S2;
    FILE *fi, *fo;
    fi = fopen("flip.in", "r");

    fo = fopen("flip.out", "w");
    fscanf(fi, "%d %d\n", &N, &M); // N linii, M coloane
    for (lin=0; lin<N; lin++) {
        for (col=0; col<M; col++)
            fscanf(fi, "%ld ", &mat[lin][col]);
        fscanf(fi, "\n");
    }
    fclose(fi);

    S_max = Sum(mat, N, M);
    //luam toate aranjarile posibile de linii
    for (bin=1; bin<=pow2[N]-1; bin++) {
        memcpy(mat2, mat, sizeof mat);
        for (lin=0; lin<N; lin++) {
            if (bin&pow2[lin])
                for (col=0; col<M; col++) mat2[lin][col] = ~mat[lin][col]+1;
        } // for lin

        //am obtinut in mat2 noua matrice.
        //cautam toate coloanele negative
        S = Sum(mat2, N, M);
        for (col=0; col<M; col++) {
            S2=0;
            for (lin=0; lin<N; lin++)
                S2 += mat2[lin][col];

            //suma acestei coloane este negativa, aflam noua suma dupa inversare
            if (S2<0) S -= 2*S2;
        } // for col
        if (S > S_max) S_max = S;
    } // for bin
    fprintf(fo, "%lld\n", S_max);
    fclose(fo);
    return 0;
}