Я пытался найти решение проблемы, описанной ниже, в течение нескольких дней.
Орехи
Сегодня Сема и Юра посетили церемонию закрытия одна олимпиада. На праздничных столах было n тарелок с орехами. I-я пластина содержит гайки ai.
За одну минуту Sema может выбрать несколько пластин и определенное число x, после чего из каждой выбранной пластины он подбирает ровно x гаек (конечно, каждая выбранная пластина должна иметь хотя бы х орехов).
Определите, через какое минимальное количество минут все гайки будут в кармане Семы.
Ввод В первой строке записано одно целое число n (1 ≤ n ≤ 50) - количество пластин с гайками.
Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 50) - количество гаек в i- ая табличка.
Вывод Вывести одно число - требуемое минимальное количество минут.
Пример ввода # 1
4 7 4 11 7
Пример вывода # 1
2
Ссылка на задание: https://www.e-olymp.com/en/problems/8769 Здесь вы можете проверить решения.
Я был бы очень признателен, если бы кто-нибудь хотя бы сказал мне, какой путь к go, чтобы найти решение п алгоритм. Спасибо.
Моими лучшими решениями были
#include <iostream>
#include <set>
using namespace std;
int main() {
int n, inputNumber;
cin>>n;
set<int> combinations, newCombinations, inputNumbers, existValuesList;
for(int i = 0; i < n; i++) {
cin>>inputNumber;
inputNumbers.insert(inputNumber);
}
for(auto inputValue = inputNumbers.begin(); inputValue != inputNumbers.end(); ++inputValue) {
for(auto combination = combinations.begin(); combination != combinations.end(); ++combination) {
if (existValuesList.find(*inputValue) != existValuesList.end())
break;
newCombinations.insert(*combination + *inputValue);
if (inputNumbers.find(*combination + *inputValue) != inputNumbers.end()) {
existValuesList.insert(*combination + *inputValue);
}
}
combinations.insert(*inputValue);
combinations.insert(newCombinations.begin(), newCombinations.end());
newCombinations.clear();
}
cout<<inputNumbers.size() - existValuesList.size();
return 0;
}
71% тестов
и
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <iterator>
using namespace std;
class Nuts {
public:
int n;
set<int> inputNumbers;
set<int> combinations;
set<int> elementary;
set<int> brokenNumbers;
map<int, set<int>> numbersBreakDown;
set<int> temporaryCombinations;
void setN() {
cin>>n;
}
void setInputNumbers() {
int number;
for(int i = 0; i < n; i++) {
cin>>number;
inputNumbers.insert(number);
}
}
void calculateCombinations() {
for(int inputNumber : inputNumbers) {
temporaryCombinations.insert(inputNumber);
for(int combination : combinations) {
calculateCombination(inputNumber, combination);
}
combinations.insert(temporaryCombinations.begin(), temporaryCombinations.end());
temporaryCombinations.clear();
}
}
void calculateCombination(int inputNumber, int combination) {
if (brokenNumbers.find(inputNumber + combination) != brokenNumbers.end()) {
return;
}
if (inputNumbers.find(combination + inputNumber) != inputNumbers.end()) {
elementary.insert(inputNumber);
brokenNumbers.insert(inputNumber + combination);
addNumbersBreakDown(inputNumber, combination, breakDownNumber(combination));
}
temporaryCombinations.insert(combination + inputNumber);
}
void addNumbersBreakDown(int inputNumber, int combination, set<int> numberBreakDown) {
set<int> temporaryNumberBreakDown;
temporaryNumberBreakDown.insert(inputNumber);
temporaryNumberBreakDown.insert(numberBreakDown.begin(), numberBreakDown.end());
numbersBreakDown.insert(pair<int, set<int>>(inputNumber + combination, temporaryNumberBreakDown));
}
set<int> breakDownNumber(int combination, int count = 5) {
set<int> numberBreakDown;
for (int i = 0; i < count; i++) {
for(int it : inputNumbers) {
if (it > combination) {
continue;
}
if (it == combination) {
numberBreakDown.insert(combination);
return numberBreakDown;
}
if (combinations.find(combination - it) != combinations.end()) {
combination = combination - it;
break;
}
}
}
}
void throwOutElementaryBrokenNumbers() {
for(pair<int, set<int>> num : numbersBreakDown) {
if (brokenNumbers.find(num.first) == brokenNumbers.end()) {
continue;
}
throwOutElementaryBrokenNumber(num);
}
}
void throwOutElementaryBrokenNumber(pair<int, set<int>> num) {
int count = 0;
for(pair<int, set<int>> num1 : numbersBreakDown) {
if (num1.first != num.first && num1.second.find(num.first) != num1.second.end()) {
count++;
if (count > 1) {
brokenNumbers.erase(num.first);
break;
}
}
}
}
void throwOutBrokenNumbers() {
for(pair<int, set<int>> num : numbersBreakDown) {
if (brokenNumbers.find(num.first) == brokenNumbers.end()) {
continue;
}
int count = 0;
for(int number : num.second) {
if (brokenNumbers.find(number) != brokenNumbers.end()) {
count++;
if (count > 1) {
brokenNumbers.erase(number);
break;
}
}
}
}
}
void getResult() {
cout<<inputNumbers.size() - brokenNumbers.size();
}
void showSet(set<int> mn) {
for (int i : mn)
cout<<i<<" ";
cout<<endl;
}
};
int main() {
Nuts task = Nuts();
task.setN();
task.setInputNumbers();
task.calculateCombinations();
task.throwOutElementaryBrokenNumbers();
task.throwOutBrokenNumbers();
task.getResult();
return 0;
}
56% тестов
и
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <iterator>
using namespace std;
set<int> getSumSet(set<int> inputValue, int sum, set<int> combinations, set<int> output = {}) {
set<int> tempComb;
bool ex = false;
for(int i = 0; i < 5; i++) {
for (int val : inputValue) {
tempComb.insert(val);
if (sum == val) {
output.insert(val);
combinations.clear();
return output;
}
for (int comb : combinations) {
if (combinations.find(comb - val) != combinations.end()) {
output.insert(val);
val = comb;
ex = true;
break;
}
}
if (ex) {
ex = false;
break;
}
}
}
return output;
}
int findLoc(set<int> numbers, int val) {
int result = 0;
for (int i : numbers) {
result++;
if (i == val) {
break;
}
}
return numbers.size() - result;
}
int main() {
int n, inputNumber;
cin>>n;
set<int> combinations, inputNumbers, copyInputNumbers, numbersForBreakdown, tempCombinations, elementaryNumbers, test;
for (int i = 0; i < n; i++) {
cin>>inputNumber;
inputNumbers.insert(inputNumber);
copyInputNumbers.insert(inputNumber);
}
elementaryNumbers.insert( *inputNumbers.begin() );
for (int number : inputNumbers) {
tempCombinations.insert(number);
if (copyInputNumbers.find(number) != copyInputNumbers.end()) {
copyInputNumbers.erase(number);
elementaryNumbers.insert(number);
}
for (int combination : combinations) {
if (copyInputNumbers.find(combination + number) != copyInputNumbers.end()) {
set<int> brN = getSumSet(inputNumbers, combination, combinations);
brN.insert(number);
copyInputNumbers.erase(combination + number);
set_difference(brN.begin(), brN.end(), elementaryNumbers.begin(), elementaryNumbers.end(), inserter(test, test.begin()));
if (findLoc(inputNumbers, combination + number) > test.size() && test.size() < 3) {
elementaryNumbers.insert(brN.begin(), brN.end());
}
brN.clear();
test.clear();
}
tempCombinations.insert(combination + number);
}
combinations.insert(tempCombinations.begin(), tempCombinations.end());
tempCombinations.clear();
}
cout<<elementaryNumbers.size();
return 0;
}
57% тестов