Cod sursa(job #727002)

Utilizator rares192Preda Rares Mihai rares192 Data 27 martie 2012 18:01:24
Problema Economie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<fstream>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;

int v[1001], n;
bool uz[50001];
vector<int> sol;

void Read()
{
	ifstream fin("economie.in");
	fin >> n;
	for(int i = 1; i <= n; ++i)
		fin >> v[i];
	
	fin.close();
}

void Solve()
{
	sort(v+1, v+n+1);
	for(int i = 1; i <= v[n]; i += v[1])
		uz[i] = 1;
	
	sol.push_back( v[1] );
	for(int i = 2; i <= n; ++i)
		if( !uz[v[i]] )
		{
			sol.push_back(v[i]);
			for(int j = 1; j + v[i] <= v[n]; ++j)
				if( uz[j] )
					uz[j + v[i] ] = 1;
		}
}

void Write()
{
	ofstream fout("economie.out");
	fout << sol.size() << '\n';
	for(int i = 0; i < (int)sol.size(); ++i)
		fout << sol[i] << '\n';
	
	fout.close();
}

int main()
{
	Read();
	Solve();
	Write();
	return 0;
}