fork download
  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
stdin
2
3 1 4
1100
1010
0000
1000
2 4 4
1111
1111
1111
0111
1011
1101
stdout
Case #1: 4
Case #2: 2