HDU1210 Eddy's 洗牌问题

ゝ一纸荒年。 2022-05-15 02:05 172阅读 0赞

Problem Description

Eddy是个ACMer,他不仅喜欢做ACM题,而且对于纸牌也有一定的研究,他在无聊时研究发现,如果他有2N张牌，编号为1,2,3..n,n+1,..2n。这也是最初的牌的顺序。通过一次洗牌可以把牌的序列变为n+1,1,n+2,2,n+3,3,n+4,4..2n,n。那么可以证明，对于任意自然数N，都可以在经过M次洗牌后第一次重新得到初始的顺序。编程对于小于100000的自然数N，求出M的值。

Input

每行一个整数N

Output

输出与之对应的M

Sample Input

20 1

Sample Output

对于这道题，首先来找规律；

假设n=4，那么排列就是1-2-3-4-5-6-7-8；经过第一次洗牌，变成5-1-6-2--7-3-8-4，便于寻找规律，排列中间用了两根杠--；

第二次洗牌：7-5-3-1--8-6-4-2；第三次洗牌：8-7-6-5--4-3-2-1；

第四次洗牌：4-8-3-7--2-6-1-5；第五次洗牌：2-4-6-8--1-3-5-7；

第六次洗牌：1-2-3-4--5-6-7-8；至此，在n=4的情况下，经过6次洗牌，排列重新归位。

接下来来追踪某个牌，1的追踪路径在排列中的位置变换是1——2——4——8——7——5——1，循环长度为6；

2的追踪路径：2——4——8——7——5——1——2，循环长度为6；3的追踪路径：3——6——3，循环长度是2；3与1,2均不同，在第二次洗牌之后就已经归位了。

所以这道题求的是每个牌的循环长度的最小公倍数。

每个牌都去算循环长度的话未免有点麻烦，这道题中有个定理，在1经过一系列变换归位时，其他牌也在这时同步归位；

所以只需要追踪1的位置变换即可。

再看上面的假设条件下的1的位置变换：1——2——4——8——7——5——1，不难看出，当位置t在整个排列前半段时，即t<=n时，变换的下一个位置是2\*t；

否则，当t在整个排列后半段时，下一个位置则是2(t-n)-1,即2\*t-(2\*n+1);

而最终当t=1，即回到最初始位置时，就找到了答案。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int main()
    {
        int n, num, sum, t;
        while(scanf("%d", &n) != EOF)
        {
            num = 0;
            sum = 0;
            t = 1;
            while(num != 1)
            {
                if(t <= n)
                {
                    t = t * 2;
                }
                else
                {
                    t = 2 * t - (2 * n + 1);
                }
                num = t;
                sum++;
            }
            printf("%d\n", sum);
        }
        return 0;
    }