首页 > 代码库 > hdu-2211 杀人游戏

hdu-2211 杀人游戏

杀人游戏

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1640 Accepted Submission(s): 348


Problem Description

不知道你是否玩过杀人游戏,这里的杀人游戏可没有法官,警察之类的人,只有土匪,现在已知有N个土匪站在一排,每个土匪都有一个编号,从1到N,每次杀人时给定一个K值,从还活着的土匪中,编号从小到大的找到K个人,然后杀掉,继续往下,直到找遍,然后继续从剩下的土匪中,编号从小到大找到第K个活着的土匪,然后杀掉。比如,现在有10个土匪,K为3,第一次杀掉3,6,9号的土匪,第二次杀掉4,8号土匪,第三次杀掉5号土匪,第四次杀掉7号土匪,第五次杀掉10号土匪,我们看到10号土匪是最后一个被杀掉的(从1到K-1的土匪运气好,不会被杀!)。现在给定你一个N和一个K,问你最后一个被杀掉的土匪的编号是多少。


Input

第一行有一个T(T<=10000),接下来有T组数据,每组中包含一个N(N<2^31)和一个K(3<=K<=100&&K<N)。


Output

对于每组数据,输出最后被杀的土匪的编号。


Sample Input

1 10 3


Sample Output

10


Author

wangye
http://acm.hdu.edu.cn/showproblem.php?pid=2211

设f(N,K)返回最后取出的编号那么f(n,k)进行第一次选后,剩下n-n/k个人,这剩下的人里最后被取出的编号为f(n-n/k,k)记为x那么它在前一次队列里的编号则是(x-1)/(k-1)+x所以f(n,k)=(x-1)/(k-1)+x 其中x=f(n-n/k,k)。

 

#include<stdio.h>
int cal(int n,int k)
{
    if(n==k)return k;
    int m=cal(n-n/k,k);
    return (m-1)/(k-1)+m;
}
int main()
{
    int _case;
    int n,k;
    scanf("%d",&_case);
    while(_case--)
    {
        scanf("%d%d",&n,&k);
        printf("%d\n",cal(n,k));
    }
    return 0;
}


还有一个类似的题。

留下的士兵

Description

N个士兵站成一行,从右到左,从1N依次编号,他们还得到一个整数M。然后这些士兵从右手边的士兵开始报数。报的数为M的倍数的士兵留在队列里,其他的士兵需要离开队列。他们重复进行这项操作直到队列中的人数小于M。举例来说,如果有10个士兵,并且M=3。第一次操作后,编号为369的士兵留在队列中。第二次操作后,编号为9的士兵留在队列中。由于队列中的士兵的数量小于M,那么编号为9的士兵就是最终留在队列里面的士兵。

现在我们想知道哪些士兵将会最终留在队列中,你能告诉我们吗?

Input

输入包含几个测试数据。每个测试数据只占单独的一行,包含两个整数nm(3 <= n <= 10^9, 2 <= m <= n)。当n=0 并且m=0的时候标志输入结束。

Output

对于每组测试数据,输出两行。第一行包含一个整数X,表示最终留下的士兵的数量。第二行包含X个整数,表示最终留下的士兵的编号。你应该把他们按照升序输出。

 

Sample Input                       Output for Sample input

10 3

8 3

0 0

1

9

2

3 6


#include<iostream>
using namespace std;

int main()
{
	//freopen("in.txt","r",stdin);
	int i,j,n,m;
	while(scanf("%d%d",&n,&m) && n!=0){
		int k=m;  //
		while(n/(k)>=m)
		{	k*=m;	}
		cout<<n/k<<endl;

		int tmp=k;
		while(tmp<=n){
			cout<<tmp<<" ";
			tmp+=k;
		}
		cout<<endl;
	}
	return 0;
}


 

hdu-2211 杀人游戏