#include <iostream> #include <map> #include <vector> #include <math.h> #include <algorithm> #include <set> #define prt(tekscik) std::cout << tekscik << std::endl #define FOR(i, w) for(int i = 0; i < w; i++) void calculate(int d) { // std::vector<std::pair<int, bool>> odleglosci; std::string c; std::cin >> c; int last = -1; int loc = 0; int ilosc_wirusow = 0; bool poczatek = true; for(char a : c) { if (a == '1') { if(!poczatek) odleglosci.push_back(std::make_pair(-ceil((loc - last - 1)), 0)); else { odleglosci.push_back(std::make_pair(-ceil(loc - last - 1), 1)); poczatek = false; } ilosc_wirusow++; last = loc; } loc++; } int max_tama = ilosc_wirusow * 2; if (!poczatek) { odleglosci.push_back(std::make_pair(-ceil(loc - last - 1), 1)); } std::sort(odleglosci.begin(), odleglosci.end()); int zaciesnianie = 0; int szczepienia = 0; for (std::pair<int, bool> odl : odleglosci) { int odl_element = - odl.first; //std::cout << "Analiza! " << odl_element << " " << odl_element - zaciesnianie * 2 - 1 << std::endl; if (odl_element - zaciesnianie * 2 < 0) break; if (!odl.second) { szczepienia += odl_element - zaciesnianie * 2 - ((odl_element - zaciesnianie * 2 >= 2) ? 1 : 0); } else { szczepienia += odl_element - zaciesnianie; } zaciesnianie += 1; } if (zaciesnianie == 0) { std::cout << "0" << std::endl; } else std::cout << c.length() - szczepienia << std::endl; } int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int n; std::cin >> n; FOR(i, n) { int d; std::cin >> d; calculate(d); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include <iostream> #include <map> #include <vector> #include <math.h> #include <algorithm> #include <set> #define prt(tekscik) std::cout << tekscik << std::endl #define FOR(i, w) for(int i = 0; i < w; i++) void calculate(int d) { // std::vector<std::pair<int, bool>> odleglosci; std::string c; std::cin >> c; int last = -1; int loc = 0; int ilosc_wirusow = 0; bool poczatek = true; for(char a : c) { if (a == '1') { if(!poczatek) odleglosci.push_back(std::make_pair(-ceil((loc - last - 1)), 0)); else { odleglosci.push_back(std::make_pair(-ceil(loc - last - 1), 1)); poczatek = false; } ilosc_wirusow++; last = loc; } loc++; } int max_tama = ilosc_wirusow * 2; if (!poczatek) { odleglosci.push_back(std::make_pair(-ceil(loc - last - 1), 1)); } std::sort(odleglosci.begin(), odleglosci.end()); int zaciesnianie = 0; int szczepienia = 0; for (std::pair<int, bool> odl : odleglosci) { int odl_element = - odl.first; //std::cout << "Analiza! " << odl_element << " " << odl_element - zaciesnianie * 2 - 1 << std::endl; if (odl_element - zaciesnianie * 2 < 0) break; if (!odl.second) { szczepienia += odl_element - zaciesnianie * 2 - ((odl_element - zaciesnianie * 2 >= 2) ? 1 : 0); } else { szczepienia += odl_element - zaciesnianie; } zaciesnianie += 1; } if (zaciesnianie == 0) { std::cout << "0" << std::endl; } else std::cout << c.length() - szczepienia << std::endl; } int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int n; std::cin >> n; FOR(i, n) { int d; std::cin >> d; calculate(d); } } |