This blog was last modified 536 days before.

Analysis

Based on the question, we know the set is a Multi Set, which means the same element is allowed to appear more than one time in this set.

This condition tells us we don't need to consider anything about element duplication (which could make things far more complex lol)

Solution

We can easily find that the question could be represented by the formula below:

Explanation

In formula above:

• ${1}$ means the number itself is an element in the set.
• ${\sum_{i=1}^{\lfloor \frac{n}{2} \rfloor }A(i)}$ means the possible add-ons to the left. (This is the most important part, take your time to think about why if you are confusing about this part)

Having this formula, it's easy to use the thought of dynamic programing to write an implementation.

Here in code, we are avoiding using recursive pattern, instead, we use for loop to start from the answer of the basic question with the smallest scale (in this case is ${A(1)}$), and gradually synthesis the solution of the question with larger scale from the ground.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using std::cin, std::cout, std::endl;
using std::fstream;
using std::string, std::vector;

using LL = long long;
const char endq = '\n';

LL readInputFromFile()
{
    fstream newFile;
    newFile.open("in.txt", std::ios::in);
    if (newFile.is_open() == false)
    {
        cout << "[UnableToReadFile] Unable to open file in.txt" << endq;
        exit(-1);
    }

    LL num;
    newFile >> num;

    // close fstream object
    newFile.close();

    return num;
}

void writeAnsToFile(LL ans)
{
    fstream newFile;
    newFile.open("out.txt", std::ios::out);
    newFile << ans;
    newFile.close();
}

LL getElementCount(LL startNum)
{
    if (startNum < 1)
    {
        return 0;
    }
    vector<LL> ansVec, sumVec;
    // answer of A(0) = 0
    ansVec.push_back(0);
    sumVec.push_back(0);
    // answer of A(1) = 1
    ansVec.push_back(1);
    sumVec.push_back(1);

    if (startNum < 2)
    {
        return ansVec[startNum];
    }

    for (LL i = 2; i <= startNum; ++i)
    {
        ansVec.push_back(1 + sumVec[i / 2]);
        sumVec.push_back(sumVec[i - 1] + ansVec[i]);
    }

    return ansVec[startNum];
}

int main()
{
    LL startNum = readInputFromFile();
    LL ans = getElementCount(startNum);
    cout << "Ans: " << ans << endl;
    writeAnsToFile(ans);
    return 0;
}

// 1000

Code Explanation

Here the function getElementCount() is the core of this algorithm.

LL getElementCount(LL startNum)
{
    if (startNum < 1)
    {
        return 0;
    }
    vector<LL> ansVec, sumVec;
    // answer of A(0) = 0
    ansVec.push_back(0);
    sumVec.push_back(0);
    // answer of A(1) = 1
    ansVec.push_back(1);
    sumVec.push_back(1);

    if (startNum < 2)
    {
        return ansVec[startNum];
    }

    for (LL i = 2; i <= startNum; ++i)
    {
        ansVec.push_back(1 + sumVec[i / 2]);
        sumVec.push_back(sumVec[i - 1] + ansVec[i]);
    }

    return ansVec[startNum];
}

ansVec.push_back(1 + sumVec[i / 2]) is actually the formula: ${A(n) = 1 + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor }A(i)}$

Notice that here we use an vector sumVec to store the summation part ${\sum_{i=1}^{\lfloor \frac{n}{2} \rfloor }A(i)}$, which is a normal mean to reduce the time complexity.