/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
1 から N の番号がついた、表裏が区別できるコインが N 枚あります。コインの表裏は長さ N の文字列 S で表され、S の i 番目の文字が 1 のときコイン i は表を向いており、0 のときコイン i は裏を向いています。
あなたは、以下の操作を 0 回以上好きな回数繰り返すことができます。
- 1\leq i < j\leq N かつ j-i\geq \bm{2} を満たす整数組 (i,j) を選ぶ。コイン i とコイン j を裏返す。
操作によって N 枚のコイン全てを裏向きにできるか判定し、可能な場合必要な操作の回数の最小値を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- 1 \leq T \leq 2\times 10^5
- 3 \leq N \leq 2\times 10^5
- S は
0,1からなる長さ N の文字列 - 入力される数値は全て整数
- 1 つの入力に含まれるテストケースについて、N の総和は 2\times 10^5 以下
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
各ケースは以下の形式で与えられる。
N S
出力
T 行出力せよ。i\ (1\leq i \leq T) 行目には、 i 番目のテストケースについて、操作によりコインを全て裏向きにできる場合は必要な操作回数の最小値を、できない場合は -1 を出力せよ。
入力例 1
5 3 101 6 101101 5 11111 6 000000 30 111011100110101100101000000111
出力例 1
1 2 -1 0 8
1 番目のテストケースについては、(i,j)=(1,3) として操作を 1 回行うと、1 回の操作でコインを全て裏向きにできます。
2 番目のテストケースについては、(i,j)=(1,3) として操作を 1 回行い、(i,j)=(4,6) として操作を 1 回行うと、2 回の操作でコインを全て裏向きにできます。
3 番目のテストケースについては、コインを全て裏向きにできないことが証明できるので、-1 を出力してください。
4 番目のテストケースについては、コインは既に全て裏向きなので、操作は必要ありません。
Score : 400 points
Problem Statement
We have N coins numbered 1 to N with two distinguishable sides. A string S represents the current state of the coins. If the i-th character of S is 1, coin i is showing heads; if that character is 0, coin i is showing tails.
You can repeat the following operation zero or more times.
- Choose a pair of integers (i,j) such that 1\leq i < j\leq N and j-i\geq \bm{2}. Flip coin i and coin j.
Determine whether it is possible to make all the N coins show tails. If it is possible, find the minimum number of operations needed.
You are given T test cases to solve.
Constraints
- 1 \leq T \leq 2\times 10^5
- 3 \leq N \leq 2\times 10^5
- S is a string of length N consisting of
0and1. - All numbers in the input are integers.
- For each input file, the sum of N over the test cases is at most 2\times 10^5.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each case is in the following format:
N S
Output
Print T lines. The i-th line (1\leq i \leq T) should contain the minimum number of operations needed to make all the coins show tails if it is possible, and -1 otherwise.
Sample Input 1
5 3 101 6 101101 5 11111 6 000000 30 111011100110101100101000000111
Sample Output 1
1 2 -1 0 8
For the first test case, you can perform the operation with (i,j)=(1,3) to make all the coins show tails in one operation.
For the second test case, you can perform the operation with (i,j)=(1,3) and then with (i,j)=(4,6) to make all the coins show tails in two operations.
For the third test case, you can prove that there is no way to make all the coins show tails, so you should print -1.
For the fourth test case, the coins already show tails, so no operation is needed.