fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define lld long long
  4. #define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  5.  
  6. int main()
  7. {
  8. 	// FASTIO;
  9.  	int test;
  10.  	cin>>test;
  11.  	lld ans = 0;
  12.  	for(int kase = 1; kase <= test; kase++)
  13.  	{
  14.  		int n,m,p;
  15.  		cin>>n>>m>>p;
  16.  
  17.  		string tmp;
  18.  		vector< string >s(n);
  19.  		set< string >forbidden;
  20.  
  21.  		vector< vector<int> >banned(p, vector<int>(2, 0));
  22.  
  23.  		for(int i=0; i<n; i++) cin>>s[i];
  24.  		for(int i=0; i<m; i++) 
  25.  		{
  26.  			cin>>tmp;
  27.  			if(forbidden.find(tmp) == forbidden.end())
  28.  			{
  29.  				forbidden.insert(tmp);
  30.  			}
  31.  		}
  32.  
  33.  		vector< vector< int > >data(p, vector<int>(2,0));
  34.  
  35.  		for(int i=0; i<p; i++)
  36.  		{
  37.  			for(int j=0; j<n; j++)
  38.  			{
  39.  				if(s[j][i] == '0') data[i][1]++;
  40.  				else data[i][0]++;
  41.  			}
  42.  		}
  43.  
  44.  		tmp = "";
  45.  		int ans = 0,tans;
  46.  		for(int i=0; i<p; i++)
  47.  		{
  48. 			if(data[i][0] < data[i][1])
  49. 			{
  50. 				tmp+="0";
  51. 				ans+=data[i][0];
  52. 			}
  53. 			else
  54. 			{
  55. 				tmp+="1";
  56. 				ans+=data[i][1];
  57. 			}
  58.  		}
  59.  
  60.  		set< string >done;
  61.  		set< pair<int,string> >trails;
  62.  		trails.insert({ans,tmp});
  63.  		while(forbidden.find(trails.begin()->second) != forbidden.end())
  64.  		{
  65.  			ans = trails.begin()->first;
  66.  			tmp = trails.begin()->second;
  67.  			trails.erase(trails.begin());
  68.  			for(int i=0; i<p; i++)
  69.  			{
  70.  				if(tmp[i] == '0')
  71.  				{
  72.  					tmp[i] = '1';
  73.  					tans = ans + (data[i][1] - data[i][0]);
  74.  					if(done.find(tmp) == done.end())
  75.  					{
  76.  						done.insert(tmp);
  77.  						trails.insert({tans,tmp});
  78.  					}
  79.  					tmp[i] = '0';
  80.  				}
  81.  				else
  82.  				{
  83.  					tmp[i] = '0';
  84.  					tans = ans + (data[i][0] - data[i][1]);
  85.  					if(done.find(tmp) == done.end())
  86.  					{
  87.  						done.insert(tmp);
  88.  						trails.insert({tans,tmp});
  89.  					}
  90.  					tmp[i] = '1';
  91.  				}
  92.  			}
  93.  		}
  94.  
  95.  		cout<<"Case #"<<kase<<": "<<trails.begin()->first<<"\n";
  96.  	}
  97.  }
  98.  
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
2
3 1 4
1100
1010
0000
1000
2 4 4
1111
1111
1111
0111
1011
1101
stdout
copy 
Case #1: 4
Case #2: 2
https://ideone.com/q13XJ2
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!