Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const long long INF = (long long) 1e16;

//int d[15][127][43][29][15],;
int g[20][5], f[20];
char str[20];
short d[15][127][43][29][15];
long long p[43][29][15][15], ways[20][200], comb[20][20];
vector < vector <long long> > dp[15][43][29][15];

long long mul(long long x, long long y) {
    return min(x * y, INF);
}

int main() {

    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j < 4; j++) {
            g[i][j] = 0;
        }
        int x = i;
        while (x % 2 == 0) {
            g[i][0]++;
            x /= 2;
        }
        while (x % 3 == 0) {
            g[i][1]++;
            x /= 3;
        }
        while (x % 5 == 0) {
            g[i][2]++;
            x /= 5;
        }
        while (x % 7 == 0) {
            g[i][3]++;
            x /= 7;
        }
    }

    p[0][0][0][0] = 1;

    for (int i = 0; i <= 42; i++) {
        for (int j = 0; j <= 28; j++) {
            for (int k = 0; k <= 14; k++) {
                for (int l = 0; l <= 14; l++) {
                    if (i != 0) {
                        p[i][j][k][l] = mul(p[i - 1][j][k][l], 2LL);
                    } else if (j != 0) {
                        p[i][j][k][l] = mul(p[i][j - 1][k][l], 3LL);
                    } else if (k != 0) {
                        p[i][j][k][l] = mul(p[i][j][k - 1][l], 5LL);
                    } else if (l != 0) {
                        p[i][j][k][l] = mul(p[i][j][k][l - 1], 7LL);
                    }
                }
            }
        }
    }

    memset(d, -1, sizeof d);

    d[0][0][0][0][0] = 0;

    for (int i = 0; i < 14; i++) {
        for (int s = 0; s <= 126; s++) {
            for (int x = 0; x <= 42; x++) {
                for (int y = 0; y <= 28; y++) {
                    for (int z = 0; z <= 14; z++) {
                        if (d[i][s][x][y][z] == -1) {
                            continue;
                        }
                        for (int dig = 1; dig <= 10; dig++) {
                            int ns = s + dig - 1;
                            int nx = x + g[dig][0];
                            int ny = y + g[dig][1];
                            int nz = z + g[dig][2];
                            int now = d[i][s][x][y][z] + g[dig][3];
                            d[i + 1][ns][nx][ny][nz] = max(d[i + 1][ns][nx][ny][nz], short(now));
                        }
                    }
                }
            }
        }
    }

    for (int i = 0; i <= 14; i++) {
        for (int j = 0; j <= 42; j++) {
            for (int k = 0; k <= 28; k++) {
                for (int l = 0; l <= 14; l++) {
                    for (int s = 126; s >= 0; s--) {
                        if (d[i][s][j][k][l] != -1) {
                            dp[i][j][k][l] = vector < vector <long long> > (s + 1, vector <long long>());
                            break;
                        }
                    }
                }
            }
        }
    }

    for (int i = 0; i <= 14; i++) {
        for (int x = 0; x <= 42; x++) {
            for (int y = 0; y <= 28; y++) {
                for (int z = 0; z <= 14; z++) {
                    for (int s = 0; s < dp[i][x][y][z].size(); s++) {
                        if (d[i][s][x][y][z] == -1) {
                            continue;
                        }
                        int l = d[i][s][x][y][z] + 1;
                        dp[i][x][y][z][s] = vector <long long> (l, 0);
                    }
                }
            }
        }
    }

    dp[0][0][0][0][0][0] = 1;

    memset(ways, 0, sizeof ways);

    for (int i = 0; i < 14; i++) {
        for (int x = 0; x <= 42; x++) {
            for (int y = 0; y <= 28; y++) {
                for (int z = 0; z <= 14; z++) {
                    for (int s = 0; s < dp[i][x][y][z].size(); s++) {
                        for (int w = 0; w < dp[i][x][y][z][s].size(); w++) {
                            if (dp[i][x][y][z][s][w] == 0) {
                                continue;
                            }
                            long long val = dp[i][x][y][z][s][w];
                            for (int dig = 1; dig <= 10; dig++) {
                                int ns = s + dig - 1;
                                int nx = x + g[dig][0];
                                int ny = y + g[dig][1];
                                int nz = z + g[dig][2];
                                int nw = w + g[dig][3];
                                ways[i + 1][ns] += val;
                                dp[i + 1][nx][ny][nz][ns][nw] += val;
                            }
                        }
                    }
                }
            }
        }
    }

    memset(comb, 0, sizeof comb);

    for (int i = 0; i <= 15; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }

    for (int t = 1; scanf("%s", str) != EOF; t++) {
        int n = strlen(str);
        int sum = 0;
        long long res = 0;
        long long prod = 1;
        for (int i = 0; i < n; i++) {
            sum += str[i] - '0';
            prod *= (str[i] - '0' + 1);
        }
        for (int i = 0; i < sum; i++) {
            res += ways[n][i];
        }
        for (int x = 0; x <= 42; x++) {
            for (int y = 0; y <= 28; y++) {
                for (int z = 0; z <= 14; z++) {
                    if (sum >= dp[n][x][y][z].size()) {
                        continue;
                    }
                    for (int w = 0; w < dp[n][x][y][z][sum].size(); w++) {
                        if (p[x][y][z][w] < prod) {
                            res += dp[n][x][y][z][sum][w];
                        }
                    }
                }
            }
        }
        for (int i = 0; i < 4; i++) {
            f[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            int dig = str[i] - '0' + 1;
            for (int j = 0; j < 4; j++) {
                f[j] += g[dig][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 9; j++) {
                if (j >= str[i] - '0') {
                    break;
                }
                int x = 0;
                int y = 0;
                int z = 0;
                int w = 0;
                int s = 0;
                for (int k = 0; k < i; k++) {
                    int dig = str[k] - '0' + 1;
                    s += dig - 1;
                    x += g[dig][0];
                    y += g[dig][1];
                    z += g[dig][2];
                    w += g[dig][3];
                }
                s += j;
                x += g[j + 1][0];
                y += g[j + 1][1];
                z += g[j + 1][2];
                w += g[j + 1][3];
                int ns = sum - s;
                int nx = f[0] - x;
                int ny = f[1] - y;
                int nz = f[2] - z;
                int nw = f[3] - w;
                if (ns < 0 || nx < 0 || ny < 0 || nz < 0 || nw < 0) {
                    continue;
                }
                if (ns >= dp[n - i - 1][nx][ny][nz].size()) {
                    continue;
                }
                if (nw >= dp[n - i - 1][nx][ny][nz][ns].size()) {
                    continue;
                }
                res += dp[n - i - 1][nx][ny][nz][ns][nw];
            }
        }
        printf("%lld\n", res);
    }

    return 0;

}