algorithms

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

main.cpp (2107B)


      1 #include <iostream>
      2 #include <cmath>
      3 #include <vector>
      4 #include <unordered_set>
      5 #include <unordered_map>
      6 #include <algorithm>
      7 #include <queue>
      8 
      9 #define ll long long
     10 
     11 using namespace std;
     12 
     13 // start from the beginning, fill with 1's until we reach ceil(k / 2), fill with 0's until we reach k total pairs, alternating on the rest
     14 
     15 bool isValid(string st, int n, int k) {
     16     int numZ = 0;
     17     int numO = 0;
     18     int numPairs = 0;
     19 
     20     for(int i = 0; i < st.size(); ++i) {
     21         if(i > 0) {
     22             if(st[i] == st[i-1]) {
     23                 numPairs += 1;
     24             }
     25         }
     26         if(st[i] == '1') {
     27             numO += 1;
     28         } else {
     29             numZ += 1;
     30         }
     31     }
     32 
     33     if(numPairs == k && abs(numZ-numO) <= 1 && st.size() == n)  {
     34         return true;
     35     }
     36     return false;
     37 
     38 }
     39 
     40 
     41 // THIS IS BAD: 110101
     42 // THIS IS BAD: 6
     43 // THIS IS BAD: 1
     44 // this case has an issue.
     45 
     46 // we want a prefix of a singular zero before our 1's otherwise we have too many 1's
     47 // 011010
     48 // can we just try both approaches?
     49 // like just try prefixing with a zero if we fail once?
     50 
     51 
     52 string generate(string bs, int n,int k) {
     53 
     54     // we do +1 here because 11 is two characters but only one pair
     55     int tgOne = (ceil((double)k / (double)2)) + 1;
     56     int tgZero = (floor((double)k / (double)2)) + 1;
     57 
     58     bool lastIsOne = false;
     59 
     60     for(int i = 0; i < tgOne; ++i) {
     61         bs += '1';
     62     }
     63     for(int i = 0; i < tgZero; ++i) {
     64         bs += '0';
     65     }
     66     while(bs.size() < n) {
     67         char last = bs[bs.size() - 1];
     68         if (last == '1') {
     69             bs += '0';
     70         } else {
     71             bs += '1';
     72         }
     73     }
     74     return bs;
     75 }
     76 
     77 
     78 int main() {
     79 
     80     int testCases, n, k;
     81     cin >> testCases;
     82 
     83     for(int z = 0; z < testCases; ++z) {
     84         cin >> n;
     85         cin >> k;
     86 
     87         string bs = generate("",n,k);
     88 
     89         if(isValid(bs, n, k)) {
     90             cout << bs << endl;
     91         } else {
     92             string bsT = generate("0",n,k);
     93             if(isValid(bsT, n, k)) {
     94                 cout << bsT << endl;
     95             } else {
     96                 cout << "-1" << endl;
     97             }
     98         }
     99     }
    100 }