MIN-MEX разрез

Ответ всегда не превосходит 2
, потому что MEX
 всей строки не больше 2
.

Ответ 0
 только в том случае, если нулей в строке нет совсем.

Теперь необходимо понять, когда ответ 1
, а когда — 2
. Сумма MEX
 равна 1
 только в том случае, если все нули образуют один отрезок без единиц. Тогда мы его вырежем, его MEX
 равен 1
, всё остальное — единицы, их MEX
 равен 0
.

Если же нули не образуют один отрезок без единиц, то найдутся два нуля, между которыми единица. Либо эти два нуля в одном отрезке, но тогда и единица с ними, то есть MEX
 равен 2
. Либо эти два нуля в двух разных отрезках, но тогда сумма MEX
 точно не меньше 2
.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T --> 0) {
        string s;
        cin >> s;
        int zeroes = count(s.begin(), s.end(), '0');
        if (zeroes == 0) {
            cout << 0 << '\n';
            continue;
        }
        int first = s.find('0');
        int last = s.rfind('0');
        if (last - first + 1 == zeroes) {
            cout << 1 << '\n';
        } else {
            cout << 2 << '\n';
        }
    }
    return 0;
}