Cod sursa(job #119249)

Utilizator stefysStefan stefys Data 30 decembrie 2007 03:35:07
Problema Jocul Flip Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.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
//#define DEBUG2

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, "%ld ", mat[lin][col]);
		fprintf(fo, "\n");
	}
	fprintf(fo, "\n\n");
}
#endif

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);
#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 DEBUG2
        fprintf(fo, "%d\n", bin);
#endif
        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
#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
        S = Sum(mat2, N, M);
        for (col=0; col<M; col++) {
            S2=0;
            for (lin=0; lin<N; lin++) {
                S2 += mat2[lin][col];
#ifdef DEBUG2
                //fprintf(fo, "S2 += %d\n", mat2[lin][col]);
#endif
             }
#ifdef DEBUG2
             fprintf(fo, "S2 = %d\n", S2);
#endif
            //suma acestei coloane este negativa, aflam noua suma dupa inversare

            if (S2<0) S -= 2*S2;
        } // for col
        if (S > S_max) {
#ifdef DEBUG2
            fprintf(fo, "Nou maxim: %ld -> %ld\n", S_max, S);
#endif
            S_max = S;
        }
    } // for bin
    fprintf(fo, "%d\n", S_max);
    fclose(fo);
}