HDU 4759 Poker Shuffle

2022-10-28 12:37:31

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

2013 ACM/ICPC Asia Regional Changchun Online

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);

        }

    }

}

码农公寓

Poker Shuffle

相关文章