fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //defines
  5. #define openin freopen("input.txt","r",stdin)
  6. #define openout freopen("output.txt","w",stdout)
  7. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  8. #define ll long long
  9. #define int long long
  10. #define mod 1000000007
  11. #define repr(i,x,y) for (__typeof(x) i=x;i>=y;i--)
  12. #define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++)
  13. #define all(c) (c).begin(),(c).end()
  14. #define ff first
  15. #define ss second
  16. #define pb push_back
  17. #define mp make_pair
  18.  
  19. /* Print pair */
  20. template <typename T,typename S>
  21. ostream & operator << (ostream &os , const pair<T,S> &v) {
  22. os << "(" ;
  23. os << v.first << "," << v.second << ")" ;
  24. return os ;
  25. }
  26. /* Print vector */
  27. template <typename T>
  28. ostream & operator << (ostream &os , const vector<T> &v) {
  29. os << "[" ;
  30. int sz = v.size() ;
  31. for(int i = 0 ; i < sz ; ++i) {
  32. os << v[i] ;
  33. if(i!=sz-1)os << "," ;
  34. }
  35. os << "]\n" ;
  36. return os ;
  37. }
  38. /* Print set */
  39. template <typename T>
  40. ostream & operator << (ostream &os , const set<T> &v) {
  41. T last = *v.rbegin() ;
  42. os << "[" ;
  43. for(auto it : v) {
  44. os << it ;
  45. if(it != last) os << "," ;
  46. }
  47. os << "]\n" ;
  48. return os ;
  49. }
  50. /* Print Map */
  51. template <typename T,typename S>
  52. ostream & operator << (ostream &os , const map<T,S> &v) {
  53. for(auto it : v) {
  54. os << it.first << " : " << it.second << "\n" ;
  55. }
  56. return os ;
  57. }
  58. int power(int a , int b)
  59. {
  60. int res = 1 ;
  61. while(b)
  62. {
  63. if(b%2) {
  64. res = (res * a) % mod ;
  65. }
  66. b/=2 ;
  67. a = (a*a) % mod ;
  68. }
  69. return res ;
  70. }
  71.  
  72. //debug
  73. #define TRACE
  74.  
  75. #ifdef TRACE
  76. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  77. template <typename Arg1>
  78. void __f(const char* name, Arg1&& arg1){
  79. cerr << name << " : " << arg1 << std::endl;
  80. }
  81. template <typename Arg1, typename... Args>
  82. void __f(const char* names, Arg1&& arg1, Args&&... args){
  83. const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  84. }
  85. #else
  86. #define trace(...)
  87. #endif
  88.  
  89. const int N = 111 ;
  90. string arr[N] ;
  91. string forbid[N] ;
  92. int cnt[2][N] ;
  93. int n , m , p ;
  94. map<pair<int,vector<int> > , int> dp ;
  95.  
  96. int solve(int idx , vector<int> &temp) {
  97. if(idx == p) {
  98. if(temp.empty()) return 0 ;
  99. return mod ;
  100. }
  101. if(dp.find({idx,temp}) != dp.end()) return dp[{idx,temp}] ;
  102. int &res = dp[{idx,temp}] ;
  103. vector<int> temp0 , temp1 ;
  104. int j = 0 ;
  105. while(j < temp.size() && forbid[temp[j]][idx] == '0') {
  106. temp0.pb(temp[j]) ; ++j ;
  107. }
  108. while(j < temp.size() && forbid[temp[j]][idx] == '1') {
  109. temp1.pb(temp[j]) ; ++j ;
  110. }
  111. res = solve(idx + 1 , temp0) + cnt[1][idx] ;
  112. res = min(res , solve(idx + 1 , temp1) + cnt[0][idx]) ;
  113. return res ;
  114. }
  115. int32_t main()
  116. {
  117. fast;
  118. #ifndef ONLINE_JUDGE
  119. freopen("B.in","r",stdin) ;
  120. freopen("output.txt","w",stdout) ;
  121. #endif // ONLINE_JUDGE
  122. int t ; cin >> t ;
  123. rep(tt,1,t) {
  124. cin >> n >> m >> p ;
  125. rep(i,1,n) cin >> arr[i] ;
  126. rep(i,1,m) cin >> forbid[i] ;
  127. memset(cnt , 0 , sizeof(cnt)) ;
  128. rep(pos,0,p-1) {
  129. rep(j,0,1) {
  130. rep(i,1,n) {
  131. cnt[j][pos] += (arr[i][pos] == ('0' + j)) ;
  132. }
  133. }
  134. }
  135. vector<pair<string,int> > bla ;
  136. rep(i,1,m) bla.push_back({forbid[i],i}) ;
  137. sort(all(bla)) ;
  138. vector<int> temp ;
  139. rep(i,0,m-1) temp.pb(bla[i].second) ;
  140. int ans = solve(0,temp) ;
  141. cout << "Case #" << tt << ": " << ans << endl ;
  142. dp.clear() ;
  143. }
  144. return 0;
  145. }
  146.  
Success #stdin #stdout 0s 4512KB
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