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

hide comments
sandeep48: 2018-12-22 06:48:00

Answer hidden in string pattern
AC in one go!

karan_yadav: 2018-05-26 13:41:15

Hint: This can be solved in linear time.

coolio_1: 2017-06-19 18:44:42

Ac in 1 go! :-D O(n) logic!!

up79: 2017-06-10 05:55:24

easy :) if you get the logic .

vengatesh15: 2017-01-25 10:15:09

AC in 1 go :-)

sushantoberoi3: 2016-11-03 13:05:01

logic just striked!!! afterall AC ;)

loay_omar: 2016-08-23 11:44:58

easy one :P

geoffreymace7: 2016-07-30 18:12:52

Length of string is less than 10^5, termination via EOF.

khalidamin51: 2016-03-25 22:29:03

Plz answer: How do I know that the input is over !!!

satyamsingh: 2016-02-23 15:13:17

my 50th :D


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