All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
There are N chairs placed in circular order. Some of the chairs are empty while others have a child sitting in it. You are required to change the places of the children so that all the children sit next to each other (i.e. they form a connected segment). You can do that by doing the following operation a number of times:
Choose a child and tell him to walk around the circle in clockwise order or anti-clockwise order until he finds the first empty chair, and tell him to sit there.
What is the minimum number of operations required to make all children sit next to each other?
The first line contains T, the number of test-cases.
The first line of each test-case contains N, the number of chairs.
The second line of each test-case contains a binary string of length N. If the i-th character is 1 then the i-th chair has a child initially. Otherwise (i.e. the i-th character is 0) it's empty.
For each test case, output a single line containing a single integer donating minimum number of operations needed.
- 1 ≤ T ≤ 5,000
- 1 ≤ sum of N in all test-cases ≤ 106
- at least one chair will be occupied
Input: 1 8 10001010 Output: 2
The initial configuration is:
1 0 0 1 0 0 0 1
We can tell the child who is boldened to move counter-clockwise, and the new configuration will be:
0 1 0 1 0 0 0 1
because he has moved to the first empty chair on his way.
Now, we again tell him to move counter-clockwise, and now the new configuration will be:
0 0 0 1 0 1 0 1
because he moved counter-clockwise, found an occupied chair, and hence kept moving. The next chair was vacant, and he sat down there.
Note that, in this example, we moved the same child twice, but this need not be the case. We can move different children in different moves.
You can check that this is the best we can do, and 2 is the minimum.
|Tags||cook79, kingofnumbers, simple|
|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, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions