> 设A，B两人分得value为i的marble分别为ai,bi个。
> 假设存在平分方法，那么可以找到一种分法满足如下条件：
> |a1-b1|<=3;
> |a2-b2|<=4;
> |a3-b3|<=5;
> |a4-b4|<=4;
> |a5-b5|<=6;
> |a6-b6|<=5;
> 证明如下：
> 1）|a1-b1|<=3;
> 假设a1-b1〉3，那么bi-ai>0(i=2,3,4,5,6)至少有一个成立，
> B可以用一个个value为i的marble交换A的i个value为1的marble.
> 从而使|a1-b1|减小。如果还有a1-b1>3成立，继续交换。
> 2）|a2-b2|<=4;
> 假设a2-b2>4那么那么bi-ai>0(i=1,3,4,5,6)至少有一个成立
> 1。如果b4-a4>0,那么B可以用1个value为4的marble交换A的2个value为2的marble.
> 2。从而使|a2-b2|减小，同理b6-a6>0成立时可以。。
> 如果有且仅有b5-a5>0成立，那么因为2*（a2-b2)>8,
> 必有b5-a5>8/5,有b5-a5>=2;
> 于是B可以用2个value为5的marble交换A的5个value为2的marble.
> 从而使|a2-b2|减小。
> 3。以后同理可证。
> 3）
> 。。。。。。。。。。
> ，。。。
> 
my code

#include <iostream>
using namespace std;
int marble[6];
const int limit[]={3,4,5,4,6,5};


bool half(int d,int next)
{
	if(d==0)
		return true;
	if(next==0)
		return false;
	int i;
	for(i=marble[next-1];i>=0;i--)
	{
		if(d>=i*next)
		{
			marble[next-1]-=i;
			if(half(d-i*next,next-1))
				return true;
			marble[next-1]+=i;
		}
	}
	return false;
}

int main()
{
	int i,test=1,sum=0;
	for(i=0;i<6;i++)
	{
		cin>>marble[i];
		if(marble[i]>limit[i])
		{
			marble[i]=limit[i]-(marble[i]-limit[i])%2;
		}
		sum+=marble[i]*(i+1);
	}
	while(sum!=0)
	{
		if(sum%2==0&&half(sum/2,6))
		{
			cout<<"Collection #"<<test++<<":"<<endl;
			cout<<"Can be divided.\n"<<endl;
		}
		else
		{
			cout<<"Collection #"<<test++<<":"<<endl;
			cout<<"Can't be divided.\n"<<endl;
		}
		sum=0;
		for(i=0;i<6;i++)
		{
			cin>>marble[i];
			if(marble[i]>limit[i])
			{
				marble[i]=limit[i]-(marble[i]-limit[i])%2;
			}
			sum+=marble[i]*(i+1);
		}
	}
	return 0;
}

• Re:搞错了 (1170) zhucheng 2004-12-09 09:35:13