Submission #634074

#	Time	Username	Problem	Language	Result	Execution time	Memory
634074		epicci23	Trol (COCI19_trol)	C++17	50 / 50	1 ms	212 KiB

trol

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n" 
#define MOD 1000000007
#define int long long
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define what_is(x) cerr << #x << " is " << x << endl;
const int N=200005;
const long long INF = LLONG_MAX;
const int INF2=(int)1e18;
const int LOG=20;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq;
typedef priority_queue<pii> max_pq;
typedef long long ll;
//sunlari dusun//
/*
 * kodu kisaltcak  fonksiyon
 * cevaba binary search ya da normal bs
 * segment tree / sparse table
 * stack
 * teklik ciftlik
 * precomputation
 * EN ONEMLISI OVERKILLEME
 * edge case dusunr
 * constraintlere bak
 * indisleri kontrol et 
 * dp
 * greedy
 * sorting
 * dfs bfs
 * sieve
*/

int sum(int a)
{
    int x=a;
  while(x>=10)
  {  
    int res=0;
    int b=x;
    while(b)
    {
      res+=b%10;
      b/=10;
    }
    x=res;
  }
  return x;
}


void solve()
{ 
  int l,r;cin >> l >> r;
  int cnt=0;
  while(sum(l)!=1 && l<=r)
  {
   // cout << "l: " << l << endl;
    cnt+=sum(l);
   // cout << "sum: " << sum(l) << endl;
    l++;
  }
  int sm=r-l+1;
  if(sm<0)
  {
    cout << cnt << endl;
    return;
  }
  int xd=sm/9;
  cnt+=xd*45;
  l+=xd*9;
  while(l<=r)
  {
    cnt+=sum(l);
    l++;
  }
  cout << cnt << endl;
}

int32_t main(){
   

     cin.tie(0); ios::sync_with_stdio(0);
     cout << fixed <<  setprecision(15);
 int t=1;cin>> t;
 
 while(t--) solve();
 
 return 0;
}

• Subtask 1: 50 / 50