Codeforces Round 849 (Div. 4) |
---|
Закончено |
Изначально у Тимура есть бинарная строка $$$^{\dagger}$$$ $$$s$$$ (возможно длины $$$0$$$). Он применил следующую операцию несколько раз (возможно ноль):
Вам дана строка, которая получилась у Тимура. Какая наименьшая возможная длина строки могла быть вначале (до выполнения всех операций)?
$$$^{\dagger}$$$ Бинарная строка это строка (возможно пустая), содержащая только символы $$$\texttt{0}$$$ или $$$\texttt{1}$$$.
Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.
Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \leq n \leq 2000$$$) — длину строки Тимура после выполнения всех операций.
Вторая строка каждого набора содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов $$$\texttt{0}$$$ или $$$\texttt{1}$$$, обозначающая финальную строку Тимура.
Для каждого набора входных данных выведите единственное неотрицательное целое число — наименьшую возможную длину изначальной строки Тимура. Обратите внимание, что изначальная строка Тимура может быть пустой, в этом случае выведите $$$0$$$.
931004011151010161010107101011011210211101011011010
1 2 5 0 3 1 0 2 4
В первом наборе входных данных, кратчайшая изначальная строка Тимура это $$$\texttt{0}$$$. К ней он применил следующую операцию: $$$\texttt{0} \to \color{red}{\texttt{1}}\texttt{0}\color{red}{\texttt{0}}$$$.
Во втором наборе, кратчайшая изначальная строка Тимура это $$$\texttt{11}$$$. К ней он применил следующую операцию: $$$\texttt{11} \to \color{red}{\texttt{0}}\texttt{11}\color{red}{\texttt{1}}$$$.
В третьем наборе, кратчайшая изначальная строка Тимура это $$$\texttt{10101}$$$ и он не применял к ней никаких операций.
В четвертом наборе, кратчайшая изначальная строка Тимура это пустая строка (обозначим её как $$$\varepsilon$$$). К ней он применил следующие операции: $$$\varepsilon \to \color{red}{\texttt{1}}\texttt{}\color{red}{\texttt{0}} \to \color{red}{\texttt{0}}\texttt{10}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{0101}\color{red}{\texttt{0}}$$$.
В пятом наборе, кратчайшая изначальная строка Тимура это $$$\texttt{101}$$$. К ней он применил следующие операции: $$$\texttt{101} \to \color{red}{\texttt{0}}\texttt{101}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{01011}\color{red}{\texttt{0}}$$$.
Название |
---|