Poker Shuffle

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 226    Accepted Submission(s): 78

Problem Description

Jason is not only an ACMer, but also a poker nerd. He is able to do a perfect shuffle. In a perfect shuffle, the deck containing K cards, where K is an even number, is split into equal halves of K/2 cards which are then pushed together in a certain way so as to make them perfectly interweave. Suppose the order of the cards is (1, 2, 3, 4, …, K-3, K-2, K-1, K). After a perfect shuffle, the order of the cards will be (1, 3, …, K-3, K-1, 2, 4, …, K-2, K) or (2, 4, …, K-2, K, 1, 3, …, K-3, K-1). 

Suppose K=2^N and the order of the cards is (1, 2, 3, …, K-2, K-1, K) in the beginning, is it possible that the A-th card is X and the B-th card is Y after several perfect shuffles?

 

 

Input

Input to this problem will begin with a line containing a single integer T indicating the number of datasets.

Each case contains five integer, N, A, X, B, Y. 1 <= N <= 1000, 1 <= A, B, X, Y <= 2^N.

 

 

Output

For each input case, output “Yes” if it is possible that the A-th card is X and the B-th card is Y after several perfect shuffles, otherwise “No”.

 

 

Sample Input

3 1 1 1 2 2 2 1 2 4 3 2 1 1 4 2

 

 

Sample Output

Case 1: Yes Case 2: Yes Case 3: No

 

 

Source

 

 

Recommend

liuyiding

 

举个例子，当n=3，每张牌的编号从0开始时：

 每次洗牌的时候，奇数在后偶数在前时，只需循环右移一下，如下：

0(000) -->0(000) -->0(000) -->0(000)

1(001) -->4(100) -->2(010) -->1(001)

2(010) -->1(001) -->4(100) -->2(010)

3(011) -->5(101) -->6(110) -->3(011)

4(100) -->2(010) -->1(001) -->4(100)

5(101) -->6(110) -->3(011) -->5(101)

6(110) -->3(011) -->5(101) -->6(110)

7(111) -->7(111) -->7(111) -->7(111)

 

奇数在前偶数在后时，只需右移一下，高位亦或1，如下（从右向左看）：

000(0) -> 100(4) -> 110(6) -> 111(7) -> 011(3) -> 001(1) -> 000(0)

001(1) -> 000(0) -> 100(4) -> 110(6) -> 111(7) -> 011(3) -> 001(1)

010(2) -> 101(5) -> 010(2) -> 101(5) -> 010(2) -> 101(5) -> 010(2)

011(3) -> 001(1) -> 000(0) -> 100(4) -> 110(6) -> 111(7) -> 011(3)

100(4) -> 110(6) -> 111(7) -> 011(3) -> 001(1) -> 000(0) -> 100(4)

101(5) -> 010(2) -> 101(5) -> 010(2) -> 101(5) -> 010(2) -> 101(5)

110(6) -> 111(7) -> 011(3) -> 001(1) -> 000(0) -> 100(4) -> 110(6)

111(7) -> 011(3) -> 001(1) -> 000(0) -> 100(4) -> 110(6) -> 111(7)

 

从上面两个表可以看出，每层的任意2个数异或的结果相同，且都为n。

 

eg：

000(0) -> 100(4) -> 110(6) -> 111(7) -> 011(3) -> 001(1) -> 000(0)

001(1) -> 000(0) -> 100(4) -> 110(6) -> 111(7) -> 011(3) -> 001(1)

010(2) -> 101(5) -> 010(2) -> 101(5) -> 010(2) -> 101(5) -> 010(2)

每行的红色数字异或，粉红色数字异或，蓝色数字异或------>都为7，所以，你懂得

 

import java.math.*;import java.util.*;public class Main{    static int n;    static Scanner cin = new Scanner(System.in);        static BigInteger rot(BigInteger x){        BigInteger tmp = x.and(BigInteger.valueOf(1));        return x.shiftRight(1).or(tmp.shiftLeft(n-1));    }        public static void main(String[] args){        int t = cin.nextInt(),    cases=0;        while(++cases <= t){            n = cin.nextInt();            BigInteger A = cin.nextBigInteger(),    X = cin.nextBigInteger();            BigInteger B = cin.nextBigInteger(),    Y = cin.nextBigInteger();            A = A.add(BigInteger.valueOf(-1));            B = B.add(BigInteger.valueOf(-1));            X = X.add(BigInteger.valueOf(-1));            Y = Y.add(BigInteger.valueOf(-1));            String ans = "No";            for(int i=0; i <= n; i++){                A = rot(A);                B = rot(B);                BigInteger tmpx = A.xor(X);                BigInteger tmpy = B.xor(Y);                if(tmpx.compareTo(tmpy)==0){                    ans = "Yes";                    break;                }            }            System.out.println("Case " + cases + ": " + ans);        }    }}