P1666. 糖果分享游戏

题目描述

若干学生围成一圈面向中心的老师。每个学生最初有偶数个糖果。当老师吹响哨子时，每个学生同时将自己的一半糖果给右边的邻居。任何最终糖果数为奇数的学生会从老师那里再得到一个糖果。游戏在所有学生的糖果数相同时结束。

编写一个程序，根据每个孩子初始的糖果数量，确定老师吹哨的次数以及每个学生最终拥有的糖果数。

输入格式

输入可能包含多个游戏。对于每个游戏，输入以学生数量$N$开始，接着是$N$个（偶数）糖果数，按逆时针方向给出每个孩子的糖果数。输入以学生数量$0$结束。每个数字独占一行。

输出格式

对于每个游戏，输出游戏进行的轮数以及每个孩子最终拥有的糖果数，两者在同一行。

输入样例 1

6
36
2
2
2
2
2
11
22
20
18
16
14
12
10
8
6
4
2
4
2
4
6
8
0

输出样例 1

15 14
17 22
4 8

提示

游戏在有限步内结束，因为：

1. 糖果的最大数量$\text{max}$永远不会增加。
2. 糖果的最小数量$\text{min}$永远不会减少。
3. 拥有多于最小数量的学生永远不会减少到最小数量。
4. 如果最大和最小糖果数不同，至少一个拥有最小数量的学生的数量会增加。

来源

Greater New York 2003

题意分析

这道题目模拟了一个环形糖果分享游戏，N个学生围成一圈，每人初始持有偶数颗糖果。游戏规则如下：每次老师吹哨时，所有学生会同时将自己糖果的一半交给右边的邻居，然后接收来自左边邻居的一半糖果。如果某学生最终持有奇数颗糖果，老师会补发一颗使其变为偶数。游戏在所有学生糖果数相同时结束。

解题思路

这道题的解题思路是通过代码直接模拟糖果分享的过程：首先读取学生数$stu$和初始糖果数组$candy$（如$for(i=0;i<stu;i++)$ $cin>>candy[i]$），然后进入主循环，每轮先用$flag$检查所有糖果是否相同（$if(candy[i]!=candy[0])$），若相同则跳出循环；否则$tim$计数增加，计算每个学生要给出的糖果$give[i]=candy[i]/2$，特别处理环形结构（$candy[stu-1]=candy[stu-1]/2+give[0]$并修正奇数），再处理其他学生（$candy[i]=candy[i]/2+give[i+1]$并修正奇数），直到所有糖果相同后输出轮数$tim$和最终糖果数$candy[0]$。

C++题解

#include<iostream>
using namespace std;
const int Max=100;
 
int main()
{
	int stu,i,candy[Max],give[Max];
	while(cin>>stu && stu!=0)
	{
		for(i=0;i<stu;i++)
			cin>>candy[i];
		int tim=0;
		while(1)
		{
			bool flag=false;
			for(i=0;i<stu;i++)           
				if(candy[i]!=candy[0])
				{
					flag=true;
					break;
				}
				if(!flag)
					break;
				tim++;
				for(i=0;i<stu;i++)   
					give[i]=candy[i]/2;
				candy[stu-1]=candy[stu-1]/2+give[0]; 
				if(candy[stu-1]%2==1)    
					candy[stu-1]++;
				for(i=0;i<stu-1;i++)   
				{
					candy[i]=candy[i]/2+give[i+1];
					if(candy[i]%2==1)
						candy[i]++;
				}
		}
		cout<<tim<<' '<<candy[0]<<endl;
	}
	return 0;
}