Cod sursa(job #561090)

Utilizator RobertBBadea Corneliu Robert RobertB Data 18 martie 2011 20:56:32
Problema Economie Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
using namespace std;

int vector[1000];
int keep[1000];


int functie( int x, int m)
{
	if( m == 0 )
	{
		return !(x%keep[0]);
	}
	else
	{
		bool OK=false;
		int j = x/keep[m];
		for( int i=j;i>=0;i-- )
		{
			if(x-keep[m]*i == 0)
			{
				return true;
			}
			OK = OK || functie( x-keep[m]*i, m-1 );
			if( OK == true )
			{
				return OK;
			}
		}
		return OK;
	}
}


int main()
{
	ifstream citire("economie.in");
	ofstream scriere("economie.out");
	int N,i;
	citire>>N;
	int t=1;
	for( i=0;i<N;i++ )
	{
		citire>>vector[i];
	}
	sort(&vector[0], &vector[N]);
	keep[0]=vector[0];
	for( i=1;i<N;i++ )
	{
		if ( !functie( vector[i],t-1 ) )
		{
			keep[t]=vector[i];
			t++;			
		}
	}
	scriere<<t<<"\n";
	for( i=0;i<t;i++ )
	{
		scriere<<keep[i]<<" ";
	}
}