Inrudit

#include <cstdio>
#include <algorithm>
FILE *fin = fopen("inrudit.in", "r"), *fout = fopen("inrudit.out", "w");
#define INF 1000000001
int fr[10], comb[1001][1001];
int s[1001], d[1002];

inline int f(int x)
{
    fr[x]--;
    int r = 1, c = 0;
    for (int j = 0; j < 10; j++)
    {
        r = std::min(1LL * INF, 1LL * comb[c + fr[j]][c] * r);
        c += fr[j];
    }
    fr[x]++;
    return r;
}

inline void solve(int k)
{
    int cnt = 0;
    for (int i = 0; i < 10; i++)
        cnt += fr[i];
    for (int i = 0; i < cnt; i++)
    {
        int x = 0;
        while (fr[x] == 0 || f(x) < k)
        {
            if (fr[x])
                k -= f(x);
            x++;
        }
        fputc(x + '0', fout);
        fr[x]--;
    }
}

int main()
{
    int k;
    fscanf(fin, "%d ", &k);
    char ch = fgetc(fin);
    int n = 0;
    while (ch != '\n')
    {
        s[++n] = ch - '0';
        if (k == 0)
            fputc(ch, fout);
        ch = fgetc(fin);
    }
    if (k == 0)
        return 0;
    for (int i = 0; i <= n; i++)
    {
        comb[i][0] = 1;
        for (int j = 1; j <= i; j++)
            comb[i][j] = std::min(INF, comb[i - 1][j - 1] + comb[i - 1][j]);
    }
    for (int i = n; i > 0; i--)
    {
        d[i] = d[i + 1];
        fr[s[i]]++;
        for (int x = s[i] + 1; x < 10; x++)
            if (fr[x] > 0)
                d[i] = std::min(INF, d[i] + f(x));
    }
    if (d[1] < k)
        fprintf(fout, "-1\n");
    else
    {
        int poz = 1;
        while (d[poz] >= k)
        {
            fr[s[poz]]--;
            poz++;
        }

        k -= d[poz];
        poz--;
        fr[s[poz]]++;

        int x = s[poz] + 1;
        while (fr[x] == 0 || k > f(x))
        {
            if (fr[x])
                k -= f(x);
            x++;
        }
        fr[x]--;
        for (int i = 1; i < poz; i++)
            fputc(s[i] + '0', fout);
        fputc(x + '0', fout);

        solve(k);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}