Question

741.pdf

The game has one simple rule: the player cannot flip a single coin,

instead, the player can choose one row (or one column) and flip all the

coins in that row (or that column) simultaneously.

The objective of the game is to find out a strategy to flip the coins so

that the number of head coins is maximized.

Can you write a program to help Tom to win this game?

Answer 1

#include<iostream>

 

using namespace std;

 

//class matrix

 

class matrix{

 

// number of rows

 

int r;

 

//no of columns

 

int c;

 

// array to store all the elements

 

int arr[100][100];

 

public:

 

//this function will get the input from the user

 

void get_matrix()

 

{

 

//take row and column

 

cin>>r;

 

cin>>c;

 

// take all the elements

 

for(int i=0;i<r;i++)

 

{

 

for(int j=0;j<c;j++)

 

{ int k;

 

cin>>k;

 

arr[i][j] = k;

 

}

 

}

 

}

 

// this function will flip the row

 

void invertrow(int r1)

 

{

 

//parse through the row and replace 1 with 0 and 0 with 1

 

for(int i=0;i<c;i++)

 

{

 

if(arr[r1][i]==0)

 

{

 

arr[r1][i]=1;

 

}

 

else

 

{

 

arr[r1][i] = 0;

 

}

 

}

 

}

 

// this function will invert the whole column

 

void invertcol(int c1)

 

{

 

//parse through the column and replace 1 with 0 and 0 with 1

 

for(int i=0;i<r;i++)

 

{

 

if(arr[i][c1]==0)

 

{

 

arr[i][c1]=1;

 

}

 

else

 

{

 

arr[i][c1] = 0;

 

}

 

}

 

}

 

// this function will calculate how many head can be possible

 

int maxhead()

 

{

 

// col1 will store the number of 1 in each column

 

// row 1 will store the number of 1 in each column

 

int col1[c];

 

int chalf = c/2;

 

int rhalf = r/2;

 

int row1[r];

 

//find the number of 1 in each column

 

for(int i=0;i<c;i++)

 

{

 

int col11 = 0;

 

for(int j=0;j<r;j++)

 

{

 

if(arr[j][i]==1)

 

col11++;

 

}

 

col1[i] = col11;

 

}

 

// if the number of 0 are more or equal than the number of 1 then flip

 

for(int i =0;i<c;i++)

 

{

 

if(col1[i]<=chalf)

 

{

 

invertcol(i);

 

}

 

}

 

//count head will find the number of head after all inversions.

 

int count_head =0;

 

//find the number of 1 in each row

 

for(int i=0;i<r;i++)

 

{

 

int row11 = 0;

 

for(int j=0;j<c;j++)

 

{

 

if(arr[i][j]==1)

 

row11++;

 

}

 

row1[i] = row11;

 

}

 

// if the number of 0 are more or equal than the number of 1 then flip

 

for(int i =0;i<r;i++)

 

{

 

if(row1[i]<=rhalf)

 

{

 

invertrow(i);

 

}

 

}

 

count_head =0;

 

//final program to calculate the number of head

 

for(int i =0;i<r;i++)

 

{

 

for(int j=0;j<c;j++)

 

{ // if the value is 1 then increase count

 

if(arr[i][j]==1)

 

count_head++;

 

}

 

}

 

return count_head;

 

}

 

};

 

int main()

 

{

 

int n ;

 

cin>>n;

 

// n represent the number of testcases.

 

matrix m[n];

 

// get all the matrix and store the object in m

 

for(int i=0;i<n;i++)

 

{

 

m[i].get_matrix();

 

}

 

//find max head and print them

 

for(int i=0;i<n;i++)

 

{

 

cout<<m[i].maxhead()<<"\n";

 

}

 

}