PEBBLE - Pebble Solver

Pebble is a popular turn-based multi-player game played by kids. In this game, all the players are given a binary string (i.e., a string consisting only of 0's and 1's) of some fixed length. The goal of the game is to convert this binary string to a string containing all 0's.

In a turn, a player is allowed to perform only one operation:- Replace a 1 by a 0 or vice-versa. But each such operation will flip the states of all the bits following the bit you changed.

Take for example, the string: 1001010. You decide to flip the 1 located at the 4th position. The new string after the operation will be : 1000101. (Note that 5th to 7th bits flipped as a result of flipping the 4th bit.)

Your small sister loves to play this game very much. So, you decide to gift her the pebble-solver software which solves this game with the minimum number of operations(how else will you make sure that she always wins?!). And we want to make sure that your software doesn't have any bugs. (he he)

Input

There are going to multiple test cases. Each test case consists of a single line which is the initial bit-string.

Edited: the maximum length of bit-string <= 1000.

Output

Output corresponding to the each test case in the following format :

"Game #x: y", where x indicates the test case number and y is the minimum number of steps required for your program to solve the game.

Example

Input:
0101
10000
00

Output:
Game #1: 3
Game #2: 2
Game #3: 0

Added by:Siddharth Kothari
Date:2010-10-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2015-03-06 17:13:19 Dinesh
how do we know much test cases are there?
2015-03-04 07:23:47 #include
AC in 1 go!!!!!!!
2015-01-10 10:36:03 UJtriumphsâ„¢
constraints??
2012-06-13 20:36:03 Darky
Nice problem!
2012-05-17 13:57:17 numerix
@Kirtika Ruchandani: If you got TLE with your Python code it was NOT OPTIMIZED. In fact you don't need any special optimization to get AC with Python.
2012-05-17 07:16:27 Kirtika Ruchandani
Weird - the time limit doesn't look too strict, yet got TLE with optimized python 2.5 code and O(n) solution. Got AC with same solution in C.
2011-05-07 21:32:34 Buda IM (retired)
After this one you can try solving TAILS. Also time limit should be stricter because simple O(N) exist.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.