Bit Flipping Game <Nissan>

3.1

9 votes
Basic Programming, Bit Manipulation, Bit manipulation, Easy, Implementation
Problem

Two players A and B are playing a game.They are given N binary numbers as input. Each binary number is represented as a string of characters '0' or '1'. The string always ends at '1'.  In one move each player decides a bit position p . Then he visits all the numbers and if their bit at that position is '1' then he changes it to '0'. It is mandatory to flip(change '1' to '0') bit of atleast one number in each move. The player who is unable to make a move loses. Player A begins the game.

Input
First line contains a number N as input. Next N lines contain a binary string each.

Output
Print A if player A wins , B otherwise. In the next line print the move number of the last move of the winning player.

Constraints
1N105
1|S|106 where |S| is sum of length of all bit strings.

 

Some important information - 
Suppose that the length of the string S in input is K then S[0] is the 0th bit , S[1] is the first bit and so on S[k1] is the (k1)th bit. All the other bit for that string are assumed as zeros. 

Note: Go through the sample explanation carefully

Sample Input
2
01
001
Sample Output
B
2
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

First string in the input is 01 so its 0th bit is 0 and 1st bit is 1. Rest all the bits are zero

Second string in the input is 001 , its 0th bit is 0 , 1st bit is also 0 and second bit is 1. Rest all the bits are zero.

First move : Player A selects the bit position 1. So first string becomes 00 and second string is 001

Second move: Player B selects the bit position 2. So first string remains 00 and second becomes 000.

Now the turn is of player A but there are no numbers which have '1' in it's binary representation so A loses and B wins. Also the last move played by the player B is 2. Hence the move number is 2.

Editor Image

?