Cod sursa(job #119235)

Utilizator stefysStefan stefys Data 30 decembrie 2007 02:49:40
Problema Jocul Flip Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <stdio.h>
#include <math.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;
}

#ifdef DEBUG
void AFIS (FILE *fo, long mat[][MAX_MAT_SIZE], unsigned int size_l, unsigned int size_c)
{
	unsigned int lin,col;
	for (lin=0; lin<size_l; lin++) {
		for (col=0; col<size_c; col++)
			fprintf(fo, "%d ", mat[lin][col]);
		fprintf(fo, "\n");
	}
	fprintf(fo, "\n\n");
}
#endif

int main (void)
{
    unsigned short 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;
    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, "%d ", &mat[lin][col]);
        fscanf(fi, "\n");
    }
    fclose(fi);
#ifdef DEBUG
    AFIS(fo, mat, N, M);
#endif
    S_max = Sum(mat, N, M);
    //luam toate aranjarile posibile de linii
    for (bin=1; bin<=pow(2.0,N)-1; bin++) {
#ifdef DEBUG
    fprintf(fo, "%d\n", bin);
#endif
        for (col=0; col<M; col++) {
            for (lin=0; lin<N; lin++) {
                if (bin&pow2[lin])
                    mat2[lin][col] = ~mat[lin][col]+1;
                else
                    mat2[lin][col] = mat[lin][col];
            } // for lin
        } // for col
#ifdef DEBUG
        fprintf(fo, "Inainte de inversare:\n");
        AFIS(fo, mat, N, M);
        fprintf(fo, "Dupa inversare:\n");
        AFIS(fo, mat2, N, M);
#endif
        //am obtinut in mat2 noua matrice.
        //cautam toate coloanele negative
        for (col=0, S=0; col<M; col++) {
            for (lin=0; lin<N; lin++)
                S += mat2[lin][col];
            if (S<0) {
                // am gasit o coloana in dezavantaj, o inversam
                for (lin=0; lin<N; lin++)
                    mat2[lin][col] = ~mat2[lin][col]+1;
            }
        S = Sum(mat2, N, M);
        if (S > S_max) S_max = S;
        } // for col
    } // for bin
    fprintf(fo, "%d\n", S_max);
    fclose(fo);
}