首页 > 代码库 > poj 1012 & hdu 1443 Joseph（约瑟夫环变形）

poj 1012 & hdu 1443 Joseph（约瑟夫环变形）

2024-07-20 16:58:37   224人阅读

题目链接：

POJ  1012: http://poj.org/problem?id=1012

HDU 1443: http://acm.hdu.edu.cn/showproblem.php?pid=1443

约瑟夫环（百度百科）: http://baike.baidu.com/view/717633.htm?fr=aladdin


Description

The Joseph‘s problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved. 

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy. 

Input

The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.

Output

The output file will consist of separate lines containing m corresponding to k in the input file.

Sample Input

3
4
0

Sample Output

5
30

Source

Central Europe 1995

题意：

       共有 k 个坏人 k 个好人坐成一圈（总人数就为2*k），前面的 k 个为好人（编号1~k），后面的 k 个为坏人(编号k+1~2k)，

现有一个报数为 m ，从编号为 1 的人开始报数，报到 m 的人会自动的死去。

求当 m 为何值时，可以使在出现有好人死亡前，k 个坏人已经全部死掉？


注意: 当前一轮第 m 个人死后，下一轮的编号为1的人是前一轮编号为 m+1 的人，

若前一轮恰好是最后一个人死掉，则下一轮循环回到开头那个人报“1”


k比较小，直接暴力打表!


代码如下：

#include <cstdio>
int main()
{
    int p[17], ans[17] = {0};
    int m, k;
    for(k = 1; k <= 14; k++)
    {
        int n = 2*k;//总人数
        m = 1;
        for(int i = 1; i <= k; i++)
        {
            //因为编号是从1开始的
            ans[i] = (ans[i-1]+m-1)%(n-i+1);
            if(ans[i] < k)//说明杀掉了好人，不符合题意
            {
                i = 0;
                m++;//枚举
            }
        }
        p[k] = m;
       // printf("%d\n",p[k]);
    }
   // return 0;
   int kk;
   while(scanf("%d",&kk) && kk)
   {
       printf("%d\n",p[kk]);
   }
   return 0;
}


poj 1012 & hdu 1443 Joseph（约瑟夫环变形）


联系
我们