1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/* 2025
 * Maciej Szeptuch
 */
#include <algorithm>
#include <cstdio>

int days;
long long int limit[1024];
int order[1024];
long long int result[1024][16];

const int MEM_LIMIT = 150000000;

char _last[MEM_LIMIT];

int last(long long int n);

int main(void)
{
    for(int l = 0; l < 10; ++l)
        _last[l] = l + 1;

    scanf("%d", &days);
    for(int d = 0; d < days; ++d)
    {
        scanf("%lld", &limit[d]);
        order[d] = d;
    }

    std::sort(order, order + days, [](int a, int b)
        { return limit[a] < limit[b]; });

    long long int current = 1;
    for(int d = 0; d < days; ++d)
    {
        while(current <= limit[order[d]])
        {
            ++result[1023][last(current) - 1];
            ++current;
        }

        for(int c = 0; c < 10; ++c)
            result[order[d]][c] = result[1023][c];
    }

    for(int d = 0; d < days; ++d)
    {
        for(int c = 0; c < 10; ++c)
            printf("%lld ", result[d][c]);

        puts("");
    }

    return 0;
}

int last(long long int n)
{
    if(n < MEM_LIMIT && _last[n])
        return _last[n];

    long long int sum = n % 10;
    n /= 10;
    while(n > 0)
    {
        sum *= n % 10;
        n /= 10;
    }

    int digit = last(sum);
    if(sum < MEM_LIMIT)
        _last[sum] = digit;

    return digit;
}