Proficient.
Put your skills to the test.

Problem summary

Choose a plus or minus sign for every cube 1³,2³,…,k³ so their signed sum equals N, using at most 30000 signs.

Source clarification. The official example prints −++++− for N=7. The displayed −+ is another accepted witness and is the deterministic output of this implementation.

Constraints

1 < N ≤ 5000000; output length ≤ 30000.

Worked example

An independently prepared example for this explanation.

7

-+

Solution analysis

1. Use a constant-sum sign block: ---++++-++++----+----+++ over any 24 consecutive cubes evaluates to 4176, regardless of the starting integer. Expanding (x+j)³ verifies that the coefficients of x³,x²,x cancel and the constant term is 4176.
2. Write N=4176q+r with 0≤r<4176. Find a short signed-cube representation for r, then append q copies of the block. Because its value is independent of the starting index, each appended block increases the sum by exactly 4176.
3. All residues 0…4175 have a representation using at most the first 17 cubes. Compute these exactly with subset-sum dynamic programming: signs sum to S−2T, where S is the sum of the first k cubes and T is the sum of cubes assigned minus signs. Store the subset mask for each reachable T. For N=7, k=2 and minus subset {1} gives −1+8=7.

Why it works

The finite subset-sum search exhausts all sign choices for each k≤17 and explicitly checks that every residue is represented before using it. Its chosen signs give exactly r. The polynomial identity makes every appended block add 4176, hence the final sum is N. The output length is at most 17+24·floor(5000000/4176)=28745, below 30000.

Watch out. The block must continue with the next cube index, not restart at 1. Its signs and length must be copied exactly. Judge output is nonunique; the displayed shorter valid sample differs from the official witness −++++−.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<string>
#include<cstdint>
using namespace std;
int main(){
    int n;
    cin>>n;
    const int modulus=4176;
    const int maximumSum=23409;
    vector<int>mask(maximumSum+1,-1);
    vector<string>representation(modulus);
    vector<bool>found(modulus,false);
    mask[0]=0;
    int sum=0;
    for(int k=1;k<=17;++k){
        int cube=k*k*k;
        for(int value=sum;value>=0;--value){
            if(mask[value]!=-1&&mask[value+cube]==-1){
                mask[value+cube]=mask[value]|(1<<(k-1));
            }
        }
        sum+=cube;
        for(int residue=0;residue<modulus;++residue){
            if(found[residue]||residue>sum||(sum-residue)%2!=0){
                continue;
            }
            int subset=mask[(sum-residue)/2];
            if(subset==-1){
                continue;
            }
            string signs(k,'+');
            for(int bit=0;bit<k;++bit){
                if((subset>>bit)&1){
                    signs[bit]='-';
                }
            }
            found[residue]=true;
            representation[residue]=signs;
        }
    }
    // The bounded exhaustive preprocessing verifies the finite construction base.
    for(bool available:found){
        if(!available){
            return 1;
        }
    }
    string answer=representation[n%modulus];
    const string block="---++++-++++----+----+++";
    for(int i=0;i<n/modulus;++i){
        answer+=block;
    }
    cout<<answer<<'\n';
}