Submission #516703

#	Time	Username	Problem	Language	Result	Execution time	Memory
516703		KoD	Trol (COCI19_trol)	C++17	50 / 50	2 ms	204 KiB

trol

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using u64 = std::uint64_t;

u64 count(const u64 N) {
    array<array<u64, 2>, 9> dp = {};
    dp[0][0] = 1;
    u64 ten = 1;
    for (int i = 0; i < 18; ++i) {
        ten *= 10;
    }
    while (ten > 0) {
        const int d = (N / ten) % 10;
        array<array<u64, 2>, 9> next = {};
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 10; ++k) {
                    if (j == 0 and k > d) continue;
                    const int ni = (i + k) % 9;
                    const int nj = j or k < d;
                    next[ni][nj] += dp[i][j];
                }
            }
        }
        dp = std::move(next);
        ten /= 10;
    }
    u64 ret = 0;
    for (int i = 0; i < 9; ++i) {
        ret += dp[i][1] * (i == 0 ? 9 : i);
    }
    return ret;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int Q;
    std::cin >> Q;
    while (Q--) {
        u64 L, R;
        std::cin >> L >> R;
        std::cout << count(R + 1) - count(L) << '\n';
    }
    return 0;
}

• Subtask 1: 50 / 50