USACO Section4.1 nuggets

Problem Summary

Given N positive integers, d[1],d[2],…d[N] (1<=N<=10, 1<=d[i]<=256), compute the largest impossible number that cannot be written as a[1]d[1]+a[2]d[2]+…+a[n]*d[n] (a[i] is non-negative integer, 1<=i<=N).
If this number does not exist, print 0.

Analysis & Solution

Only in two cases, the number does not exist:

1. d[1],d[2],…,d[N] are not relatively prime. That is,the greatest common divisor of d[1],…,d[N] is greater than 1.
2. The minimum of d[1],d[2],…,d[N] is 1.

After checking for the two cases, we can use dynamic programming to solve this. Still, there are some tricks about the upper bound of the answer:

1. Apparently, if the minimum of d[1],…,d[N] is m, and there are m consecutive numbers, then all the numbers from here on are possible.
2. If m and n are releatively prime, then the largest number we cannot make with them is B = m*n-m-n. Moreover, if m and n are not relatively prime, the answer cannot exceed B. If there is a third number l, then the upper bound must be equal to or less than B.

Code

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int maxv = 2000000000;
const int maxm = 256*256;

int n,d[10];
bool f[maxm];

int gcd(int a,int b)
{
	if(a%b==0) return b;
	return gcd(b,a%b);
}

int main()
{
	fstream fin("nuggets.in",ios::in);
	fstream fout("nuggets.out",ios::out);

	fin>>n;
	for(int i=0;i<n;i++) fin>>d[i];
	fin.close();
	sort(d,d+n);

	if(d[0]==1)
	{
		fout<<0<<endl;
		fout.close();
		return 0;
	}

	int p=d[0];
	for(int i=1;i<n;i++) p=gcd(p,d[i]);

	if(p!=1)
	{
		fout<<0<<endl;
		fout.close();
		return 0;	
	}

	f[0]=true;
	int lim=d[n-1]*d[n-2]-d[n-1]-d[n-2];
	for(int i=0;i<n;i++)
		for(int j=d[i];j<=lim;j++)
			if(f[j-d[i]])
				f[j]=true;

	int ans=0;
	for(int i=lim;i>=1;i--)
		if(!f[i])
		{
			ans=i;
			break;
		}

	fout<<ans<<endl;
	fout.close();
	return 0;
}