/*
下面的程序玩的是这样一个游戏：
有 n 只猴子，它们决定选一个作为大王。它们讨论后决定这样选大王：首先选定一个数字 m。
然后n只猴子首尾相连围成一圈，编号 1，2，3....n 。
从 编号为 1 的猴子开始报数，报到 m 的猴子出局，接着下一只猴子从 1 从新开始报数。
这样直到最后最后剩下一只猴子，它就是大王。
*/
#include<stdio.h>
struct num{int a,b;};
// 将 s 中元素使用直接选择排序的方法
//按 s[i].b(也就是出局的次序) (0<=i<n) 从小到大排序
void f(struct num s[],int n)
{
int index,j,k;
struct num temp;
for(k=0;k<n-1;k++)
{
index=k;
for(j=k+1;j<n;j++)
if(s[j].b<s[index].b) index=j;
temp=s[index];
s[index]=s[k];
s[k]=temp;
}
}
void main()
{
int count,i,k,m,n,no;
struct num s[100],*p;
// 读入猴子总数 n ，每次报到 m 出局
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<n;i++)
{
s[i].a=i+1; //猴子编号 ，从 1开始
s[i].b=0; //标志是否猴子已经出局
}
p=s; //从第一只猴子开始报数
count=no=0; //开始报数前 count =0 ，开始时出局的猴子数目为 no=0
while(no<n) // 当还有猴子没有出局，游戏继续
{
// p->b==0 ,表示猴子未出局，该猴子报数 ，即 count++
if(p->b ==0)count++;
if(count==m) // 报数到 m 的猴子出局
{
no++; // 累加已经出局的猴子数目 no
p->b=no; // 标记该猴子的出局的次序为 no
count=0; // 从新开始报数
}
p++; // 轮到下一只猴子报数
if(p==s+n) // 如果轮到最后一只猴子报数，回到第一只猴子（因为它们围成一个圈）
p=s;
}
f(s,n); // 对猴子的出局次序进行排序，最先出局的排在开始，最后出局的排在结尾
// 输出第 k 只的出局的猴子在游戏开始前，在圈里面的位置 ，如果 k = n ，
// 输出的就是 大王
printf("%d: %d\n",s[k-1].b,s[k-1].a);
}
/*
对于下面的题目，你可以不看程序，这样做：
1）在纸上写下 1，2，3 ... n 共 n个数字
2）从 1 开始数数，数到 m 时，把数到的数字划掉，并在它的下面写上 1，
划掉的数字在下次数数时直接跳过去，数到最后一个则回到开始
3）从刚划掉的数字的下一个数字开始，从新从 1 开始 数数，
数到 m 时，把数到的数字划掉，并在它的下面写上 2
....
4) 从刚划掉的数字的下一个数字开始，从新从 1 开始 数数，
数到 m 时，把数到的数字划掉，并在它的下面写上 n
如输入 5 4 3 ，(n=5,m=4,k=3)我们这样做(划掉的数字放在 "[]"里面)：
注：建议将下面内容拷贝到记事本之类的文本编辑器查看，否则可能不对齐
写下： 1 2 3 4 5
第一轮: 1 2 3 [4] 5
出局 1
第二轮: 1 2 [3] [4] 5
出局 2 1
第三轮: 1 2 [3] [4] [5]
出局 2 1 3
第四轮: 1 [2] [3] [4] [5]
出局 4 2 1 3
第五轮: [1] [2] [3] [4] [5]
出局 5 4 2 1 3
出局的次序为 queue[5] = 4 ，3，5，2，1 (下标从1开始)
输出： k ： queue[k] ，这里 k=3 ，答案为 3：5
供选择的答案：
程序运行时，输入5 4 3，输出：
A、3：5 B、2：3
C、1：2 D、4：1
答案： A
程序运行时，输入5 3 4，输出：
A、3：5 B、1：2
C、4：3 D、4：2
答案：D
程序运行时，输入7 5 2，输出：
A、1：5 B、6：1
C、2：3 D、2：4
答案：C
程序运行时，输入4 2 4，输出：
A、3：3 B、4：2
C、2：4 D、4：1
答案：D
*/
温馨提示：答案为网友推荐，仅供参考