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
2016-02-23 15:13:17
my 50th :D
2016-01-15 16:07:28 minhthai
be careful :)
2015-12-30 03:03:44 Arnab Animesh Das
Damn you output format... cost me 2WA... :(
2015-10-27 08:21:54
nice problem
2015-10-23 04:45:36 Shubhransh Srivastav
My 100th :) A long way to go...
2015-09-27 01:50:01 sarvagya
maximum length of the string ?
2015-05-17 21:05:54 Sam Winchester
what are the constraints ??
2015-04-01 19:18:25 xyz
dont forget to print Game #x: , caused me 1 WA
2015-03-30 05:28:47 Rajat (1307086)
use:
while(scanf("%s",str)!=EOF)
{
//O(n) solution
}
2015-03-29 22:45:53 Daljeet Singh
easy one!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.