algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

bad.cpp (1767B)


      1 #include <iostream>
      2 #include <vector>
      3 #include <unordered_set>
      4 #include <unordered_map>
      5 #include <algorithm>
      6 #include <queue>
      7 
      8 #define ll long long
      9 
     10 
     11 // idea:
     12 //  - just 1 + number of bits surrounded by opposite
     13 //      - uhh, no because then there are really long runs
     14 //          - so maybe just like the total number of runs of (length >= 3) + 1
     15 // - is there some sort of 1010101 thing where we can only use that once?
     16 //     - actually yeah, it seems like that's exactly it
     17 
     18 
     19 // concretely:
     20     // start at 1 for base string
     21     // increment on 101 strings and munch remaining 01010...
     22     // increment on string of >=3 0s or >=3 1s
     23 
     24 // 001011010
     25 // that should be 2
     26 
     27 // 0101010 baseline
     28 
     29 // these compress to the same thing when flipping
     30 // the first set of flipping and when we flip on the second set to:
     31 // 01010
     32 // 01010
     33 
     34 using namespace std;
     35 
     36 int main() {
     37     int testCases;
     38     string current = "";
     39     cin >> testCases;
     40 
     41     for(int z = 0; z < testCases; ++z) {
     42         cin >> current;
     43         int res = 1;
     44 
     45         bool isFlipping = false;
     46         bool isRunning = false;
     47 
     48         for(int i = 1; i < current.size()-1; ++i) {
     49 
     50             if(current[i-1] == current[i+1] && current[i] != current[i-1]) {
     51                 if(isFlipping)
     52                     continue;
     53 
     54                 // munch flipping
     55                 res += 1;
     56                 isFlipping = true;
     57             }
     58 
     59             if(current[i-1] == current[i+1] && current[i] == current[i+1]) {
     60                 // munch run
     61                 if(isRunning)
     62                     continue;
     63                 res += 1;
     64                 isRunning = true;
     65                 isFlipping = false;
     66             } else {
     67                 isRunning = false;
     68             }
     69         }
     70         cout << res << endl;
     71     }
     72 }