OpenJudge/1014.cpp at master · tongtzeho/OpenJudge · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;
bool mem[8][150000],divi;
int v[8]={0},sum,s[8]={0};
void f(const int x,const int y)
{
	if((x==1&&y<=v[1])||y==0||divi||y==s[x])
	{
		divi=1;
		return;
	}
	else if(x==1||y<0||mem[x][y]||y>s[x])return;
	int i,j=y;
	for(i=0;i<=v[x]&&j>=0;i++)
	{
		j=y-i*x;
		if(j>=0)f(x-1,j);
		if(divi)return;
	}
	mem[x][y]=1;
}
int main()
{
	int i,j=0,k;
	while(cin>>v[1]>>v[2]>>v[3]>>v[4]>>v[5]>>v[6])
	{
		divi=0;
		sum=0;
		for(i=1;i<=6;i++)
		{
			sum+=i*v[i];
			s[i]=s[i-1]+i*v[i];
		}
		if(sum==0)return 0;
		j++;
		cout<<"Collection #"<<j<<":\n";
		if(sum%2==1)
		{
			cout<<"Can't be divided.\n\n";
			continue;
		}
		for(i=1;i<=6;i++)
			for(k=0;k<=sum/2;k++)
				mem[i][k]=0;
		f(6,sum/2);
		if(divi)cout<<"Can be divided.\n\n";
		else cout<<"Can't be divided.\n\n";
	}
}