Cod sursa(job #709280)

Utilizator valentina506Moraru Valentina valentina506 Data 7 martie 2012 21:29:30
Problema Diamant Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream>
using namespace std;
int n,m,i,j,sol[250],v[250],l;
unsigned long long posibilitati;
long long cal,cmax,sum,s;

void gen(int k)
{
	int i;
	long long nr;
	if(s==sum)
		++posibilitati;
	else
		if(s<sum)
			for(i=sol[k-1]+1;i<=n*m&&v[i]<=sum-s;++i)
			{
				nr=v[i];
				if(s+nr<=sum)
				{
					s=s+nr;
					sol[k]=i;
					gen(k+1);
					s=s-nr;
				}
				if(s+2*nr<=sum)
				{
					s+=2*nr;
					sol[k]=i;
					gen(k+1);
					s-=2*nr;
				}
		}
}

int main()
{
	freopen("diamant.in","r",stdin);
	freopen("diamant.out","w",stdout);
	scanf("%d %d %lld",&n,&m,&cal);
	
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
		{
			l=(i-1)*m+j;
			v[l]=i*j;
			cmax+=i*j;
		}
		if(cmax==cal||cmax==-cal)
		    printf("1");
		
		else
		{
			sum=cmax-cal;
		    s=0;
			gen(1);
		    printf("%lld ",posibilitati);
		}
		return 0;
}