SRM405-D2-1000

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

int mem[101][101];

class IdealString {
    public:
    int req;
    vector<int> seq;
    int solve(int last, int sum) {
        if(sum > req) {
            return -2;
        }
        if(sum == req) {
            return 0;
        }
        if(mem[last][sum] != -1)
            return mem[last][sum];
        int &ret = mem[last][sum];
        ret = -2;
        for(int i = sum+1; i >= last+1; i--) {
            if(solve(i,sum+i) != -2) {
                ret = i;
                break;
            }
        }
        return ret;
    }



    void pre() {
        memset(mem,-1,sizeof(mem));
        seq.clear();
    }

    void trace(int last, int sum) {
        if(sum == req)
            return;
        int curr = solve(last,sum);
        seq.push_back(curr);
        trace(curr,sum+curr);
    }

    string construct(int length) {
        pre();
        req = length;
        int p = solve(1,1);
        if(p == -2) {
            return "";
        }
        seq.push_back(1);
        trace(1,1);
        string ans(length,'x');
        char curr = 'A';
        int num[26];
        for(int i = 0; i < seq.size(); i++) {
            ans[seq[i]-1] = curr;
            num[curr-'A'] = seq[i]-1;
            curr++;
        }
        int char_idx = 0;
        curr = 'A';
        for(int i = 0; i < length; i++) {
            if(!num[char_idx]) {
                char_idx++;
                curr++;
            }
            if(ans[i] == 'x') {
                ans[i] = curr;
                num[char_idx]--;

            }
        }
        return ans;
    }


};