贺大和他的朋友们

贺大和他的朋友们

时间: 1ms        内存:64M

描述:

贺大和他的朋友们参加一个户外训练营。训练营的项目包括爬雪山、冬泳、孤岛生存、蹦极、跳伞等极限活动。训练营规定每天淘汰表现最差的一个人。最差人选由参加活动的营员们投票决定。最后剩下的一个人将获得训练营提供的500万大奖。

贺大和他的朋友们不想因为投票伤害彼此的友谊,于是他们决定通过做游戏来决定每天出局的人选。游戏规则是这样的:将贺大和他的朋友们 n个人进行编号,分别从1到n,排成一个圈,顺时针从1开始数到m,数到m的人出局,不再参加接下来的活动。剩下的人继续参加活动,最后出局的一个人是大奖获得者。 请输出最后一个人的编号。

输入:

输入数据有多组,每组占一行,包含正整数n和m(1<=n,m<=10000)。

输出:

对于每组输入数据,输出大奖获得者的编号,每个测试实例占一行。

示例输入:

5 3
100 3

示例输出:

4
91

提示:

参考答案(内存最优[748]):

#include<stdio.h>
int main()
{
    int n,m,i,s;
	while(scanf("%d %d",&n,&m)==2)
	{
		s=0;
		for(i=2;i<=n;i++)
			s=(s+m)%i;
		printf("%d\n",s+1);
	}
	return 0;
}

参考答案(时间最优[0]):

#include <iostream>
using namespace std;
struct monkey
{
	int num;
	monkey *next;
};
monkey *head,*last;
void create(int n)
{
	int i;
	monkey *p,*q;
	p=new monkey;
	p->num=1;
	p->next=NULL;
	head=p;
	q=p;
	for(i=2;i<=n;i+=1)
	{
		p=new monkey;
		p->num=i;
		q->next=p;
		q=p;
		p->next=NULL;
	}
	last=q;
	last->next=head;
}

void select(int m)
{
	int x=0;
	monkey *p,*q;
	q=last;
	do	
	{    
		p=q->next;	
		x=x+1;			
		if(x % m==0)	                 
		{			                     
			q->next=p->next;       
			delete p;	             
			p=NULL;  
		}	             
		else q=p;		
	} while(q!=q->next);
	head = q;		
}				



int main()
{
	int n,m;			
	head=NULL;			
	while(cin>>n>>m)		
    {
		create(n);			
		select(m);
		cout<<head->num<<endl;
	}
	
	return 0;
}				

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注