|
|
SPOJ Problem Set (classical)
56. Dyzio
Problem code: 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 string, 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 begining means that the string
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 string. If you have to cut the string anyway then after the first
1 I wrote what to do with the left piece (according to the same rules as with
the whole string) and then I wrote what to do with the right piece of string
(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 string cutting. Can you write
such a program?
Task
Write a program which
- reads (from standard input) description of the way the string 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]
| Added by: | Adam Dzedzej |
| Date: | 2004-06-10 |
| Time limit: | 3s
|
| Source limit: | 50000B |
| Languages: | All |
| Resource: | Internet Contest Pogromcy Algorytmow (Algorithm Tamers)
Round III, 2003 |
|
|
|
|
RSS