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
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#ifndef TS_DEBUG
#define NDEBUG
#endif

#ifdef _WIN32
#include <io.h>
#include <fcntl.h>
#endif

#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <stdint.h>

// Brute force, bo nie umiem znaleźć reguły.
// To najgłupszy typ zadań na Potyczkach.

typedef int64_t i64;

const i64 C = 1000000;
const i64 C2 = C / 10;
i64 *Cache;

i64 zredukuj_1c(i64 x)
{
    assert(x < C);
    i64 cached = Cache[x];
    if (cached != -1) {
        return cached;
    }
    i64 save = x;
    i64 wynik = 1;
    do {
        wynik *= x % 10;
        x /= 10;
    } while (x > 0);
    Cache[save] = wynik;
    return wynik;
}

i64 zredukuj_1(i64 x)
{
    assert(x < C);
    i64 wynik = 1;
    do {
        wynik *= x % 10;
        x /= 10;
    } while (x > 0);
    return wynik;
}
i64 zredukuj_2(i64 x)
{
    i64 wynik = 1;
    while (x >= C) {
        i64 t = x % C;
        if (t < C2) return 0;
        wynik *= zredukuj_1c(t);
        x /= C;
    }
    wynik *= zredukuj_1c(x);
    return wynik;
}

i64 zredukuj_do_cyfry(i64 x)
{
    while (x >= 10) {
        x = zredukuj_2(x);
    }
    return x;
}

typedef struct {
    i64 Counts[10];
} wynik_t;

const int MaxL = 1000;
const i64 MaxN = 1000000000000000000;

int L;
i64 N[MaxL] = { 0 };
wynik_t Wyniki[MaxL] = { 0 };
int Indeks[MaxL];


int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

#ifdef _WIN32
    _setmode( _fileno( stdout ),  _O_BINARY );
#endif

    Cache = new i64[C];

    std::cin >> L;
    for (int i = 0; i < L; i++) {
        i64 n;
        std::cin >> n;
        N[i] = n;
        Indeks[i] = i;
    }
    std::sort(&Indeks[0], &Indeks[L], [](int a, int b) { return N[a] < N[b]; });

    wynik_t Wynik = { 0 };
    i64 Ostatni = N[Indeks[L-1]];

    i64 OstatniCache = (Ostatni + 1) < C ? (Ostatni + 1) : C;
    for (int i = 0; i < OstatniCache; i++) {
        Cache[i] = -1;
    }

    int NextI = 0;
    int NextN = N[Indeks[NextI]];
    for (i64 x = 1; x <= Ostatni; x++) {
        auto d = zredukuj_do_cyfry(x);
        assert(0 <= d);
        assert(d < 10);
        Wynik.Counts[d]++;
        while (x == NextN) {
            Wyniki[Indeks[NextI]] = Wynik;
            NextI++;
            NextN = NextI < L ? N[Indeks[NextI]] : MaxN;
        }
    }

    for (int i = 0; i < L; i++) {
        for (int d = 0; d < 9; d++) {
            std::cout << Wyniki[i].Counts[d] << ' ';
        }
        std::cout << Wyniki[i].Counts[9] << '\n';
    }

    std::cout.flush();

    return 0;
}