D - Magnets Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

0 と 1 のみからなる 2 つの長さ N の文字列 A = A_1A_2 \ldots A_N と B = B_1B_2 \ldots B_N が与えられます。

左右に一列に並んだ N 個のマスがあります。 i = 1, 2, \ldots, N について、左から i 番目のマスはマス i と呼ばれ、 はじめマス i には、A_i = 1 ならばコマが 1 個置かれており、A_i = 0 ならばコマは置かれていません。

下記の操作を好きな回数（ 0 回でも良い）だけ繰り返します。

  • まず、1 以上 N 以下の整数 i を選ぶ。
  • そして、すべてのコマを同時に、マス i に近づく方向に 1 マス動かす。すなわち、各コマを次が成り立つように動かす： そのコマの移動前の位置をマス j 、移動後の位置をマス j' とすると、
    • i \lt j ならば j' = j-1 、
    • i \gt j ならば j' = j+1 、
    • i = j ならば j' = j 。

上記の操作の繰り返しによって、下記の条件を満たす状態にすることが可能かを判定し、可能な場合はそれまでに操作を行う回数としてありえる最小値を求めてください。

すべての i = 1, 2, \ldots, N について次が成り立つ： B_i = 1 であるとき、かつ、そのときに限り、マス i にコマが 1 個以上存在する。

T 個の独立なテストケースが与えられるので、それぞれについて答えを出力してください。

制約

  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq N \leq 10^6
  • T, N は整数
  • A, B はそれぞれ 0 と 1 のみからなる長さ N の文字列
  • A_i = 1 である i が存在する
  • B_i = 1 である i が存在する
  • すべてのテストケースにわたる N の総和は 10^6 以下

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

ここで、i = 1, 2, \ldots, T について、\mathrm{case}_i は i 番目のテストケースを表す。

各テストケースは下記の形式で与えられる。

N
A
B

出力

T 行出力せよ。 i = 1, 2, \ldots, T について、i 行目には i 番目のテストケースに対する答えとして、 問題文中の条件を満たす状態にすることが不可能な場合は -1 を、 可能な場合はそれまでに操作を行う回数としてありえる最小値を出力せよ。

入力例 1

3
8
01001101
00001011
3
010
111
20
10100011011110101011
00010001111101100000

出力例 1

3
-1
5

入力は 3 個の独立なテストケースからなります。

1 番目のテストケースでは、 初期状態において、コマの配置、すなわち各マスに置かれているコマの個数を並べた列は (0, 1, 0, 0, 1, 1, 0, 1) です。 下記の通りに 3 回の操作を行うことで、問題文中の条件を満たす状態にすることができます。

  • 1 回目の操作として、i = 5 として操作を行う。その結果、コマの配置は (0, 0, 1, 0, 2, 0, 1, 0) となる。
  • 2 回目の操作として、i = 8 として操作を行う。その結果、コマの配置は (0, 0, 0, 1, 0, 2, 0, 1) となる。
  • 3 回目の操作として、i = 8 として操作を行う。その結果、コマの配置は (0, 0, 0, 0, 1, 0, 2, 1) となる。

一方、3 回未満の操作で問題文中の条件を満たす状態にすることはできないため、1 番目のテストケースに対する答えとして、3 を出力します。

2 番目のテストケースでは、 どのような手順で操作を行っても、問題文中の条件を満たすことはできません。 よって、2 番目のテストケースに対する答えとして、-1 を出力します。

Score : 1000 points

Problem Statement

You are given two length-N strings A = A_1A_2 \ldots A_N and B = B_1B_2 \ldots B_N, each consisting of 0 and 1.

There are N squares aligned in a row from left to right. For i = 1, 2, \ldots, N, the i-th square from the left is called square i. Initially, square i contains a piece if A_i = 1, and no piece if A_i = 0.

You may repeat the following operation any number of times (possibly zero):

  • Choose an integer i between 1 and N, inclusive.
  • Move all pieces simultaneously one square closer to square i. That is, for each piece, let square j be its current position and square j' be its new position, and the following holds:
    • if i < j, then j' = j-1;
    • if i > j, then j' = j+1;
    • if i = j, then j' = j.

Determine whether it is possible to reach a configuration satisfying the following condition, and if it is possible, find the minimum number of operations needed to do so:

For every i = 1, 2, \ldots, N, there is at least one piece in square i if and only if B_i = 1.

You are given T independent test cases. Print the answer for each of them.

Constraints

  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq N \leq 10^6
  • T and N are integers.
  • A and B are strings of length N, each consisting of 0 and 1.
  • There exists i such that A_i = 1.
  • There exists i such that B_i = 1.
  • The sum of N over all test cases is at most 10^6.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Here, \mathrm{case}_i (i=1,2,\ldots,T) denotes the i-th test case.

Each test case is given in the following format:

N
A
B

Output

Print T lines. For each i = 1, 2, \ldots, T, on the i-th line, print -1 if it is impossible to reach a configuration satisfying the condition for the i-th test case. Otherwise, print the minimum number of operations needed.

Sample Input 1

3
8
01001101
00001011
3
010
111
20
10100011011110101011
00010001111101100000

Sample Output 1

3
-1
5

The input has three independent test cases.

In the first test case, initially, the sequence of the numbers of pieces in the squares is (0, 1, 0, 0, 1, 1, 0, 1). By performing the operation three times as follows, you can satisfy the condition:

  • Choose i = 5. After the operation, the configuration is (0, 0, 1, 0, 2, 0, 1, 0).
  • Choose i = 8. After the operation, the configuration is (0, 0, 0, 1, 0, 2, 0, 1).
  • Choose i = 8. After the operation, the configuration is (0, 0, 0, 0, 1, 0, 2, 1).

It is impossible to satisfy the condition in fewer than three operations, so the answer is 3.

In the second test case, no matter how you perform the operations, you cannot satisfy the condition, so the answer is -1.