Ответ всегда не превосходит 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;
}