Cod sursa(job #485139)

Utilizator MieluNegruGabriel Bila MieluNegru Data 17 septembrie 2010 12:02:08
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

int a[16][16], copie[16][16], col[16], n, m, i, j, k, nrMax, nrCrt, sum;

void citire() {
	ifstream fin("flip.in");
	fin>>n>>m;
	for (i=0;i<n;i++)
		for (j=0;j<m;j++)
			fin>>a[i][j];
	fin.close();
}

int main() {
	citire();
	//initializam copia
	for (i=0; i<n; i++)
		for (j=0; j<m; j++)
			copie[i][j]=a[i][j];
	
	//generam toate combinatiile de coloane
	//initial col[i]==0 pentru orice i
	//daca col[i]==1 inseamna ca am comutat coloana i
	int x = 0, y = (int) pow(2.0f,m);
	while (x<y) {
		nrCrt = 0;
		for (j=0; j<m; j++) {
			if (col[j]==1) {
				for (i=0; i<n; i++)
					copie[i][j] = -a[i][j];
			} else
				for (i=0; i<n; i++)
					copie[i][j] = a[i][j];
		}
		
		/*
		for (i=0;i<n;i++) {
			for (j=0;j<m;j++)
				cout<<copie[i][j]<<' ';
			cout<<endl;
		}
		cout<<endl;
		*/
		
		for (i=0; i<n; i++) {
			sum = 0;
			for (j=0;j<m;j++)
				sum += copie[i][j];
			sum = sum * (sum>0 ? 1 : -1);
			nrCrt += sum;
		}
		if (nrCrt > nrMax) 
			nrMax = nrCrt;
		
		for (k=m-1; k>=0; k--) {
			if (col[k]==1) {
				col[k] = 0;
			}
			else {
				col[k]=1;
				break;
			}
		}
		x++;
	}	
	
	ofstream fout("flip.out");
	fout<<nrMax;
	fout.close();
	
	return 0;
}