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
//Wojciech Filipek
#include "bits/stdc++.h"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int dlug[n];
    string tab[n];
    for(int i = 0; i < n; i++){
        cin >> dlug[i] >> tab[i];
    }
    
    int wynik = 0;

    bool war = true;
    int poczatek = 0;
    int dlugo = 0;
    int pocztest = 0;
    int dlugtest = 0;
    for(int j = 0; j < n; j++){
        war = true;
        while(war == true){
        poczatek = 0;
        dlugo = 0;
        pocztest = 0;
        dlugtest = 0;
        for(int i = 0; i < tab[j].length(); i++){
            if(tab[j][i] == '0'){
                if(pocztest == -1)
                    pocztest = i;
                dlugtest++;
                //cout << "len:" << tab[j].length() << " i: " << i << " dlugtest: " << dlugtest << " dlug: " << dlugo << endl;
                if(i == tab[j].length()-1){
                    if((dlugtest > dlugo && 
                    (tab[j][pocztest-1] == '1' || tab[j][pocztest+dlugtest] == '1')) || (dlugtest == dlugo && ((tab[j][pocztest-1] == '1' &&
                    tab[j][pocztest+dlugtest] != '1') || (tab[j][pocztest-1] != '1' && tab[j][pocztest+dlugtest] == '1')))){
                        dlugo = dlugtest;
                        poczatek = pocztest;
                    }
                }
            }
            else if(tab[j][i-1] != tab[j][i] && tab[j][i] == '1'){
                if((dlugtest > dlugo && 
                    (tab[j][pocztest-1] == '1' || tab[j][pocztest+dlugtest] == '1')) || (dlugtest == dlugo && ((tab[j][pocztest-1] == '1' &&
                    tab[j][pocztest+dlugtest] != '1') || (tab[j][pocztest-1] != '1' && tab[j][pocztest+dlugtest] == '1')))){
                    dlugo = dlugtest;
                    poczatek = pocztest;
                }
                pocztest = -1;
                dlugtest = 0;
            }
        }
        //cout << poczatek << " " << dlugo << endl; //miejsce i dlugosc nadluzszego ciagu 0

        if(dlugo != 0){
            if(tab[j][poczatek-1] == '1'){
                tab[j][poczatek] = 'x';
            }
            else{
                tab[j][poczatek+dlugo-1] = 'x';
            }
            for(int i = 0; i < tab[j].length(); i++){
                if(tab[j][i] == '0' && (tab[j][i-1] == '1' || tab[j][i+1] == '1'))
                    tab[j][i] = '2';
            }
            for(int i = 0; i < tab[j].length(); i++){
                if(tab[j][i] == '2')
                    tab[j][i] = '1';
            }
            //cout << tab[j] << endl;   //ciąg po wstawieniu x
        }
        else{
            for(int i = 0; i < tab[j].length(); i++){
                if(tab[j][i] == '1')
                    wynik++;
            }
            cout << wynik << endl;
            wynik = 0;
            war = false;
        }
        }
    }
}