Submission #1244298

#TimeUsernameProblemLanguageResultExecution timeMemory
1244298minhpkTrol (COCI19_trol)C++20
50 / 50
0 ms328 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
int query(int n){
    int res=0;
    while (n>0){
         res+=n%10;
         n/=10;
    }
    if (res>=10){
        return query(res);
    }
    return res;
}
int convert(int n){
    int v=n%9;
    if (v==0){
        return 9;
    }
    return v;
}
int pre;
void solve(){
    int l,r;
    cin >> l >> r;
    int res=0;
    if (r-l+1<=20){
        for (int i=l;i<=r;i++){
             res+=query(i);
        }
        cout << res << "\n";
        return;
    }
    while (l%10!=1){
         res+=query(l);
         l++;
    }
    while (r%10!=0){
         res+=query(r);
         r--;
    }
//    cout << l << " " << r << "\n";
    int sl=(r-l+1)/10;
    res+=sl*pre;
    int sta=(l-1)/10+1;
    int sta1=(r-1)/10+1;
    int l1=1;
    int r1=sl;
    if (sl<=20){
//        cout << res << " ";
        for (int i=sta;i<=sta1;i++){
           //  cout << i << " " << convert(i) << "\n";
             res+=convert(i);
        }
        cout << res << "\n";
       // cout << "ok" << "\n";
        return;
    }
    while (sta%9!=1){
         res+=convert(sta);
         sta++;
         l1++;
    }
    while (sta1%9!=0){
         res+=convert(sta1);
         sta1--;
         r1--;
    }
    res+=(r1-l1+1)/9*pre;
    cout << res << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    for (int i=1;i<=9;i++){
         pre+=i;
    }
    while (t--){
         solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...