【ZCMU2069】分糖果

點選打開連結

2069: 分糖果

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 38  Solved: 28

[Submit][Status][Web Board]

Description

　有n個小朋友圍坐成一圈。老師給每個小朋友随機發偶數個糖果，然後進行下面的遊戲：

　　每個小朋友都把自己的糖果分一半給左手邊的孩子。

　　一輪分糖後，擁有奇數顆糖的孩子由老師補給1個糖果，進而變成偶數。

　　反複進行這個遊戲，直到所有小朋友的糖果數都相同為止。

　　你的任務是預測在已知的初始糖果情形下，老師一共需要補發多少個糖果。

Input

       程式首先讀入一個整數N(2<N<100)，表示小朋友的人數。

接着是一行用空格分開的N個偶數（每個偶數不大于1000，不小于2）

Output

要求程式輸出一個整數，表示老師需要補發的糖果數。

Sample Input

32 2 4

Sample Output

4

HINT

Source

曆屆試題

解題思路：

要注意小朋友分糖果的時候都是同時進行的，是以要定義一個新的數組b記錄每次給左邊的小朋友分的糖果的個數，在别人的部落格上看到一個很有趣的說法。最開始小朋友都将糖果放在左手中，别人給自己的糖果放在右手中，一輪結束後左手中的原糖果數減半+右手中的糖果數即為一輪後的糖果數，再進行判斷是否為奇數。

代碼：

#include<cstdio>
#include<iostream>
using namespace std;
int a[10001],b[10001],n;
bool is_equal()
{
	for(int i=0;i<n-1;i++){
		if(a[i]!=a[i+1])return false;
	}
	return true;
}
int main()
{
	cin>>n;
	int ans=0,i;
	for(i=0;i<n;i++)cin>>a[i];
	while(1){
		if(is_equal())break;
		b[n-1]=a[0]/2;
		for(i=1;i<n;i++)b[i-1]=a[i]/2;
		for(i=0;i<n;i++){
			a[i]=(a[i]-a[i]/2)+b[i];
			if(a[i]%2!=0){
				ans++;
				a[i]=a[i]+1;
			}
		}
		/*for(i=0;i<n;i++)cout<<a[i]<<" ";
		cout<<endl;*/
	}
	cout<<ans<<endl;
	return 0;
}