All submissions for this problem are available.Today is the day of the CCDSAP exam. Chef is responsible for monitoring the exam. The hall in which the exam will be held contains $N$ seats (numbered $1$ through $N$) arranged in a row. Initially, each seat is either empty or occupied by a participant in the exam. You are given a binary string $S$ with length $N$; for each valid $i$, the $i$-th character of $S$ is '1' if the $i$-th seat is occupied or '0' if this seat is empty. Chef wants to make sure that no two participants are sitting next to each other, in order to prevent cheating. To do this, Chef may perform a number of operations (possibly zero). In each operation, he can ask a participant to move from his seat to an adjacent seat, either to its left or right, if such a seat exists and is empty. Find the minimum number of operations required to make sure that no two participants are sitting next to each other (in adjacent seats), or determine that it is impossible. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains a single integer $N$. - The second line contains a single string $S$ with length $N$. ### Output For each test case, print a single line containing one integer ― the minimum number of operations, or the string `"impossible"` if Chef cannot achieve his goal. ### Constraints - $1 \le T \le 10,000$ - $1 \le N \le 2 * 10^5$ - the sum of $N$ over all test cases does not exceed $ 2 * 10^5$ - the exam has at least one participant ### Subtasks **Subtask #1 (50 points):** the sum of $N$ over all test cases does not exceed $5,000$ **Subtask #2 (50 points):** original constraints ### Example Input ``` 4 3 011 5 10111 1 1 6 000111 ``` ### Example Output ``` 1 impossible 0 3 ```
|Tags||dynamic-programming, kingofnumbers, ltime80, medium-hard, slope-trick, taran_1407|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.