Submission #1248649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248649		hayyy	Trol (COCI19_trol)	C++20	50 / 50	0 ms	328 KiB

trol

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

// Count how many numbers from 1 to X have each digital root 1 to 9
vector<ll> count_droots_up_to(ll X) {
    vector<ll> counts(10, 0); // index 1-9 used
    ll full_cycles = X / 9;
    ll remainder = X % 9;

    for (int i = 1; i <= 9; ++i) {
        counts[i] = full_cycles;
        if (i <= remainder) counts[i]++;
    }
    return counts;
}

int main() {
    ll N;
    cin >> N;
    while (N--) {
        ll A, B;
        cin >> A >> B;

        vector<ll> cntB = count_droots_up_to(B);
        vector<ll> cntA = count_droots_up_to(A - 1);

        ll ans = 0;
        for (int i = 1; i <= 9; ++i) {
            ans += i * (cntB[i] - cntA[i]);
        }

        cout << ans << endl;
    }
}

• Subtask 1: 50 / 50