Posted in GCJ

GCJ Post #5

Continuing with my said goal ( solving 5 problems per day) This is what I did for the 2 days…

((งง •̀•̀__•́•́))งง


I had planned to put 5 problems of the GCJ types and discuss post and lot picked one for the next 2 weeks until July 10th.But I suddenly felt that I was going too easy on myself , so I started doing 20 sums a day since yesterday until I am not able to do 20 sums per day…

So the list of problems that were chosen the last 2 days were:

  1. The Best Box
  2. Little Elephants and Permutation
  3. The Probability Of Winning
  4. N Different Palindromes
  5. Tourist Transalations
  6. Open the Dragon Scroll
  7. Uncle Johny
  8. Farmer Feb
  9. Digital Clock
  10. Code Crazy Minions

So the lot picked problem for today is 

Open the Dragon Scroll

The problem statement :

Did you ever hear about ‘Dragon Food’ ? It’s used to refer to the chocolates bought for your loved ones :). Po offers dragon food to master Shifu, who is a famous cook in the valley of food. In return, Shifu hands over the dragon scroll to Po, which is said to hold the ingredients of the secret recipe. To open the dragon scroll, one has to solve the following puzzle.

1. Consider a N-bit integer A. We call an integer A’ as shuffle-A, if A’ can be obtained by shuffling the bits of A in its binary representation. For eg. if N = 5 and A = 6 = (00110)2, A’ can be any 5-bit integer having exactly two 1s in it i.e., any of (00011)2, (00101)2, (00110)2, (01010)2, …., (11000)2.

2. Given two N-bit integers A and B, find the maximum possible value of (A’ xor B’) where A’ is a shuffle-A, B’ is a shuffle-B and xor is the bit-wise xor operator.

Given N, A and B, please help Po in opening the dragon scroll.

Notes 1. xor operator takes two bit strings of equal length and performs the logical XOR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 OR only the second bit is 1, but will be 0 if both are 1 or both are 0. For eg: 5 (0101) xor 3(0011) = 6(0110). In most languages it is represented using ^ symbol. 5 ^ 3 = 6.
2. If the integer actually needs less than N bits to represent in binary, append sufficient number of leading 0 bits. For eg. as shown in the problem statement for N = 5, A = 6 = (00110)2

Input

First line contains an integer T ( number of test cases, around 100 ). T cases follow, each having N A B in a single line, separated by a space. ( 1 <= N <= 30, 0 <= A,B < 2N )

Output

For each case, output the maximum possible value of (shuffle-A xor shuffle-B) in a separate line.

Example

Input

3
3 5 4
5 0 1
4 3 7

Output

7
16
14

Explanation

We need to make A^B maximum by shuffling the 1 bits within A and B. As 1 ^ 0 = 0 ^ 1 = 1, we need to make maximum number of (1,0) or (0,1) pairs, where a pair means the corresponding bits from A and B at a particular bit position. Also, to make the result maximum, we want all the ones towards the most significant side (left). Lets pair each 1 bit of A with a 0 bit of B. There can be at max x = minimum _ of( number of 1s in A, number of 0s in B). Similarly, pair each 1 bit of B with a 0 bit of A. There can be at max y = minimum _ of( number of 1s in B, number of 0s in A). Rest of the pairs are either (1,1) or (0,). So, the number of ones in the result is at max P = x + y. The answer is (1111…) : P times followed by (…000) : N-P times, which is nothing but the integer ( ((1<

So the code I came up with is this…well it works so I have no issue I guess…? 

n=int(input())
for i in range(n):
    a,b,c=input().split()
    a=int(a)
    b=int(b)
    c=int(c)
    b=bin(b)[2:]
    c=bin(c)[2:]
    b=b.count(“1”)
    c=c.count(“1”)
    d=abs(a-(b+c))

    print(2**a-2**d) 

┤* ̄O ̄*├ 

┤*-.-*├ 

┤_ _├




Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s