SHARE
TWEET

Untitled

a guest Sep 15th, 2019 101 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <string.h>
  5. #include <unordered_map>
  6. using namespace std;
  7. #define endl '\n'
  8. #define pi pair<int, int>
  9.  
  10. unordered_map<int, int> used;
  11.  
  12. int recur(int x){
  13.     if(used.find(x) != used.end()) return used[x];
  14.    
  15.     int ret = __builtin_popcount(x);
  16.    
  17.     for(int i = 0; i < 24; i++){
  18.         if(((x >> i) & 7) == 3){
  19.             ret = min(ret, recur(x - (3 << i) + (4 << i)));
  20.         }
  21.         if(((x >> i) & 7) == 6){
  22.             ret = min(ret, recur(x - (6 << i) + (1 << i)));
  23.         }
  24.     }
  25.    
  26.     return used[x] = ret;
  27. }
  28.  
  29. void answer(){
  30.     int k;
  31.     string s;
  32.     cin >> k >> s;
  33.    
  34.     int n = 0;
  35.     for(int i = 0; i < s.size(); i++) n = (n << 1) | (s[i] == '-');
  36.    
  37.     cout << k << " " << recur(n) << endl;
  38. }
  39.  
  40. int main(){
  41.     ios::sync_with_stdio(false);
  42.     cin.tie(NULL);
  43.    
  44.     int p;
  45.     cin >> p;
  46.    
  47.     for(int i = 0; i < p; i++) answer();
  48.  
  49.     return 0;
  50. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top