algorithms

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

main.cpp (1302B)


      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 // n seats
     11 // no sitting next to each other
     12 // binary string for occupancy 
     13 
     14 // Your task is to calculate the minimum total number of students seated when it is impossible to seat anyone else in the row
     15 
     16 
     17 using namespace std;
     18 
     19 int main() {
     20 
     21     int testCases;
     22     cin >> testCases;
     23 
     24     for(int z = 0; z < testCases; ++z) {
     25         int n;
     26         string current;
     27         cin >> n;
     28         cin >> current;
     29 
     30         ll sum = 0;
     31         for(int i = 0; i < current.size(); ++i) {
     32             if(current[i] == '1')
     33                 sum += 1;
     34         }
     35 
     36 
     37         for(int i = 0; i < current.size(); ++i) {
     38             if(current[i] == '1') {
     39                 continue;
     40             }
     41             if(i > 0 && current[i-1] == '1') {
     42                 continue;
     43             }
     44             if(i + 1 < current.size() && current[i+1] == '1') {
     45                 continue;
     46             }
     47             if(i + 1 < current.size() && !(i + 2 < current.size() && current[i+2] == '1')) {
     48                 current[i+1] = '1';
     49             }
     50             else {
     51                 current[i] = '1';
     52             }
     53             sum += 1;
     54         }
     55         
     56         cout << sum << endl;
     57     }
     58 }