# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
516703 |
2022-01-22T00:41:05 Z |
KoD |
Trol (COCI19_trol) |
C++17 |
|
2 ms |
204 KB |
#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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
2 ms |
204 KB |
Output is correct |