Cod sursa(job #2501177)

Utilizator mircearoataMircea Roata Palade mircearoata Data 29 noiembrie 2019 10:25:59
Problema Economie Scor 10
Compilator cpp-64 Status done
Runda simu Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream in("economie.in");
ofstream out("economie.out");

int n, pref;
int v[1005];
bool posibil[50005];
vector<int> ansV;

bool ok()
{
	for (int i = pref + 1; i <= n; i++)
		if (!posibil[v[i]])
			return false;
	return true;
}

int main()
{
	posibil[0] = 1;
	in >> n;
	for (int i = 1; i <= n; i++)
		in >> v[i];
	sort(v + 1, v + n + 1);
	while (!ok())
	{
		pref++;
		for (int i = 0; i <= v[n] - v[pref]; i++)
			posibil[i + v[pref]] = posibil[i + v[pref]] || posibil[i];
	}
	for (int i = 1; i <= pref; i++)
	{
		bool isDiv = false;
		for (int x : ansV)
			if (v[i] % x == 0)
			{
				isDiv = true;
				break;
			}
		if (!isDiv)
			ansV.push_back(v[i]);
	}
	out << ansV.size() << '\n';
	for (int x : ansV)
		out << x << '\n';
}