首页 > 代码库 > 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个士兵站成一行,从右到左,从1到N依次编号,他们还得到一个整数M。然后这些士兵从右手边的士兵开始报数。报的数为M的倍数的士兵留在队列里,其他的士兵需要离开队列。他们重复进行这项操作直到队列中的人数小于M。举例来说,如果有10个士兵,并且M=3。第一次操作后,编号为3,6,9的士兵留在队列中。第二次操作后,编号为9的士兵留在队列中。由于队列中的士兵的数量小于M,那么编号为9的士兵就是最终留在队列里面的士兵。
现在我们想知道哪些士兵将会最终留在队列中,你能告诉我们吗?
Input
输入包含几个测试数据。每个测试数据只占单独的一行,包含两个整数n和m(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 杀人游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。