DYZIO - Dyzio


Dyzio is Jasiek's friend and he also likes riddles. Here is a riddle he came up with:

Jasiek, here is a piece of rope, which has to be cut into smaller pieces. I will not tell you directly how to do it, but look at this sequence of zeros (0) and ones (1). A one at the beginning means that the rope has to be cut in half. If the first digit was zero, it would be the only digit in the sequence and mean you don't have to cut anything - I want the whole rope. If you have to cut the rope anyway then after the first 1 I wrote what to do with the left piece (according to the same rules as with the whole rope) and then I wrote what to do with the right piece of rope (all the time with the same rules of notation). Every time you have to cut the left piece first, only then can you cut the right one. Now start cutting and tell me, how many cuts you have to do until you have cut off the shortest piece.

Unfortunately mom hid the scissors from Jasiek, but luckily a computer was at hand and Jasiek quickly wrote a program simulating the rope cutting. Can you write such a program?

Task

Write a program which

  • reads (from standard input) description of the way the rope is cut,
  • counts how many cuts have to be made in order to get the first shortest piece.
  • writes out the outcome (to standard output)

Input

Ten test cases (given one under another, you have to process all!). Each test case consists of two lines. In the first line there is a number n (1<=n<=20000). In the second line one zero-one word (a sequence of zeros and ones without spaces between them) of length n - the description of the cutting procedure given by Dyzio.

Output

For every testcase your program should write (to the standard output) only one line with one integer equal to the number of cuts which have to be made in order to get the shortest piece.

Example

Input:
9
110011000
[and 9 test cases more]

Output:
4
[and 9 test cases more]

hide comments
lokesh_2052: 2021-03-15 05:55:03

Hi guy's
When I solved this question this was solved by only 1039 people
I spent more then two hours

------Spoiler Alert-----------
please spend more then hour then look at this

<snip>

Some useful testcase that help me to understand this problem in more good manner

INPUT:
9
110011000
9
111000100
3
010
1
1
2
11
15
111100111000000
15
101010110011000
19
1100111011001010000
13
1100111000100
15
111010001010100
OUTPUT:
4
3
0
1
2
7
7
9
5
4

Last edit: 2023-02-20 21:32:58
jkelava6: 2019-03-21 21:24:11

Word 'string' is being used for two different things here!
1) Binary string which defines the way you cut
2) A string(very thin rope) that you are cutting
This causes a LOT of confusion!

dwij28: 2017-09-24 01:18:04

To get accepted in Python, use sys.setrecursionlimit(20000), otherwise it will end up in an NZEC. Got several NZECs due to that. Also use, try catch in an infinite loop with break on exception while reading input.

ashishranjan28: 2016-12-17 07:54:02

easy recursion :)

Anubhav Gupta: 2015-09-21 06:59:26

Done without recursion :)

(Tjandra Satria Gunawan)(曾毅昆): 2015-08-18 09:49:58

For those who confuse / didn't completely understand problem description you can go to forum (discuss) and search "DYZIO" there are clear sample case explanation by tripleM on the forum.

agaurav77: 2015-01-11 14:29:20

As tainic says, indeed, this one is a beautiful question. :)

Rishav Goyal: 2014-05-28 16:59:26

how to put this problem in tutorial -:)

John and the cows: 2013-08-15 13:44:50

length(string) div 2+1, I think ????

Sayan Paul: 2013-05-16 02:58:11

how to divide a string in half when its length is odd


Added by:Adam Dzedzej
Date:2004-06-10
Time limit:1.903s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Internet Contest Pogromcy Algorytmow (Algorithm Tamers)
Round III, 2003