This May, a group of exchange students come to HIT. They would like to play a game. Firstly, they stand in a circle. Then they choose the Mth student as the first and count off one by one (for example, the first calls 1,the second calls 2 and so on). Every time when one calls number K, he will be out of the circle, and the rest continue the game and his next student will be the new first. The last one to leave the circle will be the winner of the round. Now the question is who will be winner of each round?

Hint:You can solve the problem with a circular linked list.
Input and output data format:
Input
First line: a number N indicates the number of the students;
The following n lines: each line is a name which is a string without any digit whose maximum length is 20.
The next lines:each line shows one round and there are two numbers M and K.
Output
For each round, you need to output one line represents the name of the winner in the round.
Sample:
Input
4
Tom
Jack
Sol
Free
2 3
3 2

Output

Jack

Sol

Interpretation:
The first round:

Jack 1, Sol 2, Free 3,     Free out;

Tom 1,Jack 2, Sol 3,      Sol out;

Tom 1,Jack 2, Tom 3,    Tom out;

Jack is the winner.

3天了，无人跟贴，俺来顶一下，作为抛砖引玉吧：
约瑟夫环问题详解：
1.首先，我们先来了解一下什么是约瑟夫环问题：

讲一个比较有意思的故事：约瑟夫是犹太军队的一个将军，在反抗罗马的起义中，他所率领的军队被击溃，只剩下残余的部队40余人，他们都是宁死不屈的人，所以不愿投降做叛徒。一群人表决说要死，所以用一种策略来先后杀死所有人。
于是约瑟夫建议：每次由其他两人一起杀死一个人，而被杀的人的先后顺序是由抽签决定的，约瑟夫有预谋地抽到了最后一签，在杀了除了他和剩余那个人之外的最后一人，他劝服了另外一个没死的人投降了罗马。
我们这个规则是这么定的：
在一间房间总共有n个人（下标0～n-1），只能有最后一个人活命。
按照如下规则去杀人：
。所有人围成一圈
。顺时针报数，每次报到q的人将被杀掉
。被杀掉的人将从房间内被移走
。然后从被杀掉的下一个人重新报数，继续报q，再清除，直到剩余一人
你要做的是：当你在这一群人之间时，你必须选择一个位置以使得你变成那剩余的最后一人，也就是活下来。
2.这就是约瑟夫环问题，接下来我们说个特例初步了解下这种问题的求解思路：
特例：2，当q = 2时候，是一个特例，能快速求解
特例还分两种：
1.思路：注意这里的前提是n = 2^k(也就是2的幂次个人，其他数另外讨论)
如果只有2个人，显然剩余的为1号。
如果有4个人，第一轮除掉2,4，剩下1,3，3死，留下1。
如果是8个人，先除去2,4,6,8,之后3,7，剩下1,5，除去5，又剩下1了，
定义J(n)为n个人构成的约瑟夫环最后结果，则有j(2^k) = 1
J(n) = 2^k – 2^k-1 = 2^k-1                  n=2^k
J(n) = 2^k-1 – 2^k-2 = 2^k-2                n=2^k-1
………
J(2^2) = 2^2 – 2^1 = 2^1                    n=2^2
递推得到如上结果，起始我们仔细分析也就是每次除去一半的元素，然后剩余的一半继续重复之前的策略，再除去一半。（可想到递归）
结合：J(2) = 1 我知道两个数，从1开始，肯定是2先死，剩下1.
2.but当n 不等于 2^k时候，比如9,11这种：
n 不等于 2^k时，就不存在这样的easy的规律了，重新分析，
我们干掉第一个人也就是2，之后就只剩下8个人了，又回到J(2^k)上了，这时候我们需要的是找到当前的1号元素。 这时候，我们从3号开始，就成了另外一个规模小1的约瑟夫问题（恰好为2^k的特例）。
这时候，我们可以把3号看成新的约瑟夫问题中的1号位置：
J(8) = J(2^3) = 1，也就是说这里的1代表的就是上一个问题中的3号。
同理可知所有的非2^k的数都是这样：

假设n = 2^k + t，t可以随意取，比如1，2，3…….

假设n = 11，这时候n = 2^3 + 3，也就是说t = 3，所以开始剔除元素直到其成为2^k问题的约瑟夫问题。
So，我们在剔除了t（3）个元素之后（分别是2,4,6），此时我们定格在2t+1（7）处，并且将2t+1（7）作为新的一号，而且这时候的约瑟夫环只剩下2^3，也就是J(2^3 + 3) = 2*3 + 1 = 7，答案为7。
总结一下这个规律：
J(2^k + t) = 2t+1
3.说完了特例，现在说说q 不等于2的情况下：

当q ≠ 2：

我们假定：
- n — n人构成的约瑟夫环
- q — 每次移除第q个人
约定：
- Jq(n)表示n人构成的约瑟夫环，每次移除第q个人的解
- n个人的编号从0开始至n-1

我们沿用之前特例的思想：能不能由Jq(n+1)的问题缩小成为J(n)的问题（这里的n是n+1规模的约瑟夫问题消除一个元素之后的答案），Jq(n)是在Jq(n+1)基础上移除一个人之后的解。也就是说，我们能由Jq(n)得到Jq(n+1)。
规律：Jq(n+1) = ( Jq(n) + q ) / (n+1)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node
{
    int num;
     struct Node *next;
}LinkList;
LinkList *creat(int n)
{
    int i = 1;
    LinkList *p,*q,*head;
    p = (LinkList*)malloc(sizeof(LinkList));
    p->num = i;
    head = p;
    for(i = 2;i<=n;i++)
    {
      q = (LinkList*)malloc(sizeof(LinkList));
      q->num = i;
      p->next = q;
      p = q;
      //p->next = head;
    }
    p->next = head;
    return head;
}
void fun(LinkList *L,int k,int m)
{
    int i,j;
    LinkList *p,*q,*s;
    p = L;
    for(i = 1;i<k;i++)
    {
      q = p;
      p = p->next;
    }
    while(p->next!=p)
    {
        for(j = 1;j<m;j++)
        {
            q=p;
            p = p->next;
        }
        printf("%5d",p->num);
        s = p;
        q->next = p->next;
        p = p->next;
        free(s);
    }
    printf("%5d",p->num);
}
int main()
{
    LinkList *L;
    int n,k,m;
    n = 9;
    m = 4;
    k = 2;
    L=creat(n);
    fun(L,k,m);
}

讲解得很详细~