fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef unsigned long long int ll;
  4. ll a[22];
  5. ll po[18];
  6. int dig(ll n){
  7.     int cnt=0;
  8.     while(n){
  9.         cnt++;
  10.         n/=10;
  11.     }
  12.     cnt=max(cnt,1);
  13.     return cnt;
  14. }
  15. ll np(ll n,int k){
  16.     k--;
  17.     //cout<<k<<endl;
  18.     //int f=k/2;
  19.     //cout<<f<<' '<<po[f]<<endl;
  20.     ll p=po[k/2]+(n-1);
  21.     //cout<<p<<endl;
  22.     //printf("%lld",p);
  23.     ll sum=p;
  24.     if(k%2==0)p/=10;
  25.     while(p){
  26.         sum*=10;
  27.         sum+=p%10;
  28.         p/=10;
  29.     }
  30.     return sum;
  31. }
  32. ll bs(ll n,ll lo,ll hi,int d,bool ck){
  33.     int cnt=0;
  34.     while(lo<hi){
  35.         //cout<<lo<<' '<<hi<<' '<<n<<endl;
  36.         //if(cnt==10)break;
  37.         cnt++;
  38.         ll mid=(lo+hi)/2;
  39.         ll val=np(mid,d);
  40.         if(val==n){
  41.             lo=mid;
  42.             break;
  43.         }
  44.         if(val<n)lo=mid+1;
  45.         else hi=mid-1;
  46.     }
  47.     if(lo<hi){
  48.         ll v1=np(hi,d);
  49.         if(v1<=n)lo=hi;
  50.     }
  51.     //cout<<np(lo,d)<<' '<<lo<<endl;
  52.     if(!ck && np(lo,d)>n)lo--;
  53.     //if(ck && np(lo,d)>n)lo++;
  54.     if(ck && np(lo,d)>=n)lo--;
  55.     //cout<<np(lo,d)<<' '<<lo<<endl;
  56.     return lo;
  57. }
  58. int main(){
  59.     po[0]=1;
  60.     for(int i=1;i<=17;i++){
  61.         po[i]=po[i-1]*10;
  62.     }
  63.     a[0]=0;
  64.     a[1]=10;
  65.     a[2]=a[1]+9;
  66.     ll ss=9;
  67.     for(int i=3;i<=18;i++){
  68.         if(i&1)ss*=10;
  69.         a[i]=a[i-1]+ss;
  70.     }
  71.     //for(int i=1;i<=19;i++)cout<<a[i]<<' ';cout<<endl;
  72.     int t,c=0;
  73.     scanf("%d",&t);
  74.  
  75.     while(t--){
  76.         ll x,y;
  77.         scanf("%lu%lu",&x,&y);
  78.         if(x>y)swap(x,y);
  79.         int f1=dig(x);
  80.         int f2=dig(y);
  81.         ll val=a[f2-1]-a[f1-1];
  82.         ll lo=0,hi=a[f2]-a[f2-1];
  83.         if(f2>1)val+=bs(y,lo,hi,f2,0);
  84.         else val=y+1;
  85.         hi=a[f1]-a[f1-1];
  86.         if(x>1)val-=bs(x,lo,hi,f1,1);
  87.         else val-=x;
  88.         printf("Case %d: %lu\n",++c,val);
  89.     }
  90.  
  91. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
4
1 10
100 1
1 1000
1 10000
stdout
copy 
Case 1: 9
Case 2: 18
Case 3: 108
Case 4: 198
https://ideone.com/UqS9XD
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!