| Codeforces Global Round 18 |
|---|
| Закончено |
У вас есть особая версия меноры: она состоит из $$$n$$$ свечей и некоторые из них уже зажжены. Мы можем описать, какие из свечей горят, с помощью бинарной строки $$$s$$$, где $$$i$$$-я свечка горит тогда и только тогда, когда $$$s_i=1$$$.
Первоначально, горящие свечки описаны строкой $$$a$$$. За одну операцию, вы можете выбрать любую горящую в данный момент свечку — выбранная свеча продолжит гореть, а каждая из других свечей изменит свое состояние (если она горела, то потухнет, а если не горела — то загорится).
Вы хотите, чтобы в результате свечи горели так, как описывает строка $$$b$$$. Ваша задача определить, возможно ли это и какое наименьшее количество операций нужно будет совершить.
В первой строке задано одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов.
В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1\le n\le 10^5$$$) — количество свечей.
Во второй строке каждого набора задана строка $$$a$$$ длины $$$n$$$, состоящая из символов 0 и 1 — первоначально состояние свечей.
В третьей строке задана строка $$$b$$$ длины $$$n$$$, состоящая из символов 0 и 1 — желаемое состояние свечей.
Гарантируется, что сумма $$$n$$$ не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите наименьшее количество операций, чтобы превратить $$$a$$$ в $$$b$$$, или же $$$-1$$$, если это невозможно.
5 5 11010 11010 2 01 11 3 000 101 9 100010111 101101100 9 001011011 011010101
0 1 -1 3 4
В первом наборе входных данных, две строки уже равны, а потому нам не нужно применять ни одной операции.
Во втором наборе, мы можем применить одну операцию, выбрав вторую свечку, и превратить $$$01$$$ в $$$11$$$.
В третьем наборе, невозможно применить ни одной операции, потому что нет ни одной горящей свечи, которую можно выбрать.
В четвертом наборе, мы можем применить следующие операции, чтобы превратить $$$a$$$ в $$$b$$$:
- Выберем $$$7$$$-ю свечу: $$$100010{\color{red}1}11\to 011101{\color{red} 1}00$$$.
- Выберем $$$2$$$-ю свечу: $$$0{\color{red} 1}1101100\to 1{\color{red} 1}0010011$$$.
- Выберем $$$1$$$-ю свечу: $$${\color{red}1}10010011\to {\color{red}1}01101100$$$.
В пятом наборе, мы можем применить следующие операции, чтобы превратить $$$a$$$ в $$$b$$$:
- Выберем $$$6$$$-ю свечу: $$$00101{\color{red}1}011\to 11010{\color{red}1}100$$$
- Выберем $$$2$$$-ю свечу: $$$1{\color{red}1}0101100\to 0{\color{red}1}1010011$$$
- Выберем $$$8$$$-ю свечу: $$$0110100{\color{red}1}1\to 1001011{\color{red}1}0$$$
- Выберем $$$7$$$-ю свечу: $$$100101{\color{red}1}10\to 011010{\color{red}1}01$$$
