Cod sursa(job #119425)

Utilizator flaviousasp flav flavious Data 31 decembrie 2007 13:02:41
Problema Jocul Flip Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 3.23 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;
}

/*#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int **readmatrix(FILE *,int*,int*);
void printmatrix(int **,int,int);

int comutalinia(int **,int,int);
int comutacoloana(int**,int,int,int);

int main(void) {
	FILE *in;//,*out;
	int *linii,*coloane;
	int **matrix;
	
	linii = malloc(sizeof(int));
	coloane = malloc(sizeof(int));
	in = fopen("flip.in","r");
	matrix = readmatrix(in,linii,coloane);
	//printf("linii %d coloane %d\n",*linii,*coloane);
	printmatrix(matrix,*linii,*coloane);
	int t = comutalinia(matrix,*coloane,0);
	printf("\n");
	printmatrix(matrix,*linii,*coloane);
	printf("\ndelta %d",t);
	free(linii);
	free(coloane);

	return EXIT_SUCCESS;
}

int **readmatrix(FILE *in,int *n,int *m) {
	int i,j;
	int **r;
	fscanf(in,"%d",n);
	fscanf(in,"%d",m);
	r = malloc(*n*sizeof(int*));	
	for(i=0;i<*n;i++) {
		*(r+i) = malloc(*m * sizeof(int));
		for(j=0;j<*m;j++) {
			fscanf(in,"%d",(*(r+i)+j));
		}
	}
	return r;
}

void printmatrix(int **matrix,int n,int m) {
	int i,j;
	for(i=0;i<n;i++) {
		for(j=0;j<m;j++) {
			printf("%d\t",*(*(matrix+i)+j));
		}
		printf("\n");
	}
}

int comutalinia(int **matrix,int coloane,int linia) {
	int i,s1=0,s2=0;
	for(i=0;i<coloane;i++) {
		s1 += *(*(matrix+linia)+i);
		*(*(matrix+linia)+i) = ~*(*(matrix+linia)+i)+1;
		s2 += *(*(matrix+linia)+i);
	}
	return s2-s1;
}
int comutacoloana(int **matrix,int linii,int coloane,int coloana) {
	int i,s=0;
	
	return s;
}*/