Submission #1258513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258513		damasen	Trol (COCI19_trol)	C++20	10 / 50	1 ms	328 KiB

trol

#include <bits/stdc++.h>

using namespace std;

inline int find_step (int num){
    if (num < 10) return num;
    int sum = 0;
    while(num > 0){
        sum += num%10;
        num /= 10;
    }
    return find_step(sum);
}

int triangular_sum(int n){
    return (n * (n+1)) / 2;
}

int main(){
    int q;
    cin >> q;
    while(q--){
        long long l, r;
        cin >> l >> r;
        int l_step = find_step(l);
        int r_step = find_step(r);
        long long ans = 0;
        if (r-l+1 <= 9){
            for (int i = 0; i < r-l+1; i++){
                ans += l_step;
                if(l_step < 9) l_step++;
                else if (l_step == 9) l_step = 1;
            }
            cout << ans << '\n';
            continue;
        }
        ans += 45 - triangular_sum(l_step - 1);
        ans += triangular_sum(r_step);
        long long range = r - l + 1;
        range - r_step; range - (10-l_step);
        long long sequence = range / 9;
        ans += sequence * 45;
        cout << ans << '\n';
    }
}

• Subtask 1: 10 / 50