URAL/1658

来自"NOCOW"

#include <cstdio>
#include <cstring>
#define NOANS -2
#define UNKNOWN -1
#define MaxSum 901
#define MaxSquare 8101
#define MaxDigits 100
int f[MaxSum][MaxSquare], p[MaxSum][MaxSquare], N, m, n;
bool CanUpdate(int a, int b)
{
    if (b == NOANS || b > MaxDigits-1) return 0;
    if (a == NOANS) return 1;
    return (a > b+1);
}
 
int find(int n, int m)
{
    int j;
    if (n > 9*MaxDigits || m > 81*MaxDigits || n < 0 || m < 0 || n > m) return NOANS;
    if (f[n][m] != UNKNOWN) return f[n][m];
    f[n][m] = NOANS;
    for (int i = 1; i < 10; ++i)
    {
        j = find(n-i,m-i*i);
        if (CanUpdate(f[n][m], j))
        {
            f[n][m] = j+1;
            p[n][m] = i;
        }
    }
    return f[n][m];
}
 
void print(int ans, int n, int m)
{
    if (ans == NOANS)
        printf("No solution\n");
    else
    {
        int a[9], i;
   memset(a, 0, sizeof(a));
        while (p[n][m])
        {
            i = p[n][m];
            a[i-1]++;
            n -= i;
            m -= i*i;
        }
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < a[i]; ++j)
                printf("%d", i+1);
        }
        printf("\n");
    }
}
 
int main()
{
    memset(f, -1, sizeof(f));
    f[0][0] = 0;
    scanf("%d", &N);
    while (N--)
    {
        scanf("%d%d", &n, &m);
        print(find(n, m), n, m);
    }
}