Submission #209328

#	Time	Username	Problem	Language	Result	Execution time	Memory
209328		papa	Trol (COCI19_trol)	C++14	50 / 50	5 ms	376 KiB

trol

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int q;
ll l,r;

//caka je u tome sto je taj niz periodican
//jer suma cifara daje isti ostatak kao i sam taj broj
//pa ce onda redom da budu 1,2,3,4,5,6,7,8,9,1...
//pronadjemo granice i onda samo vidimo koliko se takvih intervala pojavljuje

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cerr.tie(0);

   cin >> q;

   while(q--)
   {
       cin >> l >> r;
       ll sol = 0;
       if(r-l<=(ll)20)
       {
            //cout << "ovde" << "\n";
            for(ll i=l;i<=r;i++)
            {
                if(i%(ll)9 == (ll)0) sol+=(ll)9;
                else sol+=(ll)(i%(ll)9);
            }
            cout << sol << "\n";
       }
       else
       {
             while(1)
             {
               if((l%(ll)9)==(ll)1) break;
               else
               {
                   sol+=((l%(ll)9)==(ll)0) ? 9 : (l%(ll)9);
                   l++;
               }
             }
             while(1)
             {
               if((r%(ll)9)==(ll)0) break;
               else
               {
                   sol+=(r%(ll)9);
                   r--;
               }
             }

             ll cnt = (r-l+1)/(ll)9;
             sol+=cnt*(ll)45;
             cout << sol << "\n";
         }
   }

   return 0;
}

• Subtask 1: 50 / 50