Non-Adjacent Flip

AtCoder

IDarc156_a

Time2000ms

Memory256MB

Difficulty—

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 `0` and `1`. * 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$ [samples]

Samples

Input #1

5
3
101
6
101101
5
11111
6
000000
30
111011100110101100101000000111

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.

API Response (JSON)

{
  "problem": {
    "name": "Non-Adjacent Flip",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc156_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments