欢迎访问==> 【考研OR保研】机试题
题目描述
一些学生围坐一圈,中间站着他们的老师,所有人都面向老师。
他们要玩一个有关糖果分享的游戏。
每个学生最开始都有一定数量的糖果(保证一定是偶数)。
每轮游戏的进程为:
- 老师吹起哨声,所有学生同时拿出自己一半数量的糖果,递给右边相邻的同学。
- 传递完成后,所有拥有奇数数量糖果的同学都将再得到一颗糖果。
游戏将不断进行,直到所有学生拥有的糖果数量均相等为止。
现在,给定所有学生的初始糖果数量,请确定游戏进行的总轮次数以及游戏结束后每个学生的糖果数量。
输入格式
输入可能包含多组数据。
每组数据第一行包含整数 $N$,表示学生数量。
接下来 $N$ 行,以逆时针方向描述每个学生的初始糖果数量,每行包含一个整数。
当输入一行 $N=0$ 时,表示输入结束。
输出格式
每组数据输出一个结果,占一行。
首先输出游戏总轮次,然后输出游戏结束后每个人的糖果数量。
游戏一定会在有限轮次内结束,原因如下:
设每轮游戏开始前,拥有最多糖果的人的糖果数量为 $max$,拥有最少糖果的人的糖果数量为 $min$,那么:
- 每轮过后,$max$ 的值都不会增加。
- 每轮过后,$min$ 的值都不会减少。
- 某轮开始前,拥有糖果数量大于 $min$ 的所有人在该轮结束后,拥有的糖果数量也一定大于该轮开始前的 $min$。
- 某轮开始前,如果 $min$ 和 $max$ 不相等,那么至少一个拥有 $min$ 个糖果的人在该轮结束后,拥有糖果数量会增加。
数据范围
$1 \\le N \\le 100$,
每个学生的初始糖果数量不超过 $100$,且一定是偶数。
每个输入最多包含 $100$ 组数据。
输入样例:
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
输出样例:
15 14
17 22
4 8
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, a[N], t[N];
void turn()
{
//特殊处理第一位同学
t[0] = a[0];
t[0] -= a[0] / 2; //先将手中的一半分给下一名同学
t[0] += a[n - 1] / 2; //获得前面同学手中的一半
if(t[0] % 2 != 0) t[0] += 1; //判断交换完后是否为偶数
for(int i = 1; i < n; i ++)
{
t[i] = a[i];
t[i] -= a[i] / 2;
t[i] += a[i - 1] / 2;
if(t[i] % 2 != 0) t[i] += 1;
}
for(int i = 0; i < n; i ++) a[i] = t[i];
}
//判断游戏是否结束
bool check()
{
for(int i = 1; i < n; i ++)
{
if(a[i] != a[i - 1]) return false;
}
return true;
}
int main()
{
while(cin >> n && n != 0)
{
for(int i = 0; i < n; i ++) cin >> a[i];
int res = a[0], cnt = 0;
while(true)
{
if(check()) { res = a[0]; break; }
else { turn(); cnt ++; }
}
cout << cnt << ' ' << res << endl;
}
return 0;
}