Cod sursa(job #1477182)

Utilizator mike93Indricean Mihai mike93 Data 25 august 2015 18:06:46
Problema Jocul Flip Scor 60
Compilator c Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
#define NMAX 16
#define MMAX 16

int evaluate(int t[NMAX][MMAX], int N, int M) {
	int i, j;
	int val = 0;
	for(i=0; i<N; i++) {
		for(j=0; j<M; j++) {
			val = val + t[i][j];
		}
	}
	return val;
}

void increment(int tab[MMAX+1]) {
	int i;
	tab[0]++;
	for(i=0; i<MMAX; i++) {
		tab[i+1] = tab[i+1] + tab[i]/2;
		tab[i] = tab[i]%2;
	}
}

void invert(int t[NMAX][MMAX], int M, int k) {
	int j;
	for(j=0; j<M; j++) {
		t[k][j] = -t[k][j];
	}
}

int flip(int t[NMAX][MMAX], int N, int M) {
	int tab[MMAX+1];
	int i, j;
	for(j=0; j<M+1; j++) {
		tab[j] = 0;
	}
	int res = 0;
	while(tab[M]==0) {
		int test[NMAX][MMAX];
		for(i=0; i<N; i++) {
			for(j=0; j<M; j++) {
				if(tab[j]==0) {
					test[i][j] = t[i][j];
				} else {
					test[i][j] = -t[i][j];
				}
			}
		}
		int val = evaluate(test, N, M);
		for(i=0; i<N; i++) {
			invert(test, M, i);
			int newVal = evaluate(test, N, M);
			if(newVal > val) {
				val = newVal;
			} else {
				invert(test, M, i);
			}
		}
		if(val > res) {
			res = val;
		}
		increment(tab);
	}
	return res;
}

int main() {
	FILE* fin = fopen("flip.in", "r");
	int t[NMAX][MMAX];
	int N, M;
	fscanf(fin, "%d %d\n", &N, &M);
	int i, j;
	for(i=0; i<N; i++) {
		for(j=0; j<M; j++) {
			fscanf(fin, "%d", &t[i][j]);
		}
		fscanf(fin, "\n");
	}
	fclose(fin);
	
	int res = flip(t, N, M);
	
	FILE* fout = fopen("flip.out", "w");
	fprintf(fout, "%d\n", res);
	fclose(fout);
	return 0;
}