Saleh127

Light OJ 1205 / Implementation - B. Search

Oct 21st, 2021
731
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-21-16.49.31
  3. ***/
  4.  
  5. ///It can be solved using Digit DP
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. #define ll long long
  10. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  11. #define get_lost_idiot return 0
  12.  
  13. ll checkevn(ll n)
  14. {
  15.      ll ans=n;
  16.      while(n)
  17.      {
  18.           ans*=10;
  19.           ans+=(n%10);
  20.           n/=10;
  21.      }
  22.      return ans;
  23. }
  24.  
  25. ll checkodd(ll n)
  26. {
  27.      ll ans=n;
  28.      n/=10;
  29.      while(n)
  30.      {
  31.           ans*=10;
  32.           ans+=(n%10);
  33.           n/=10;
  34.      }
  35.      return ans;
  36. }
  37.  
  38. ll bsearchodd(ll n)
  39. {
  40.      ll l=0,h=999999999,mid;
  41.      ll ans=0;
  42.  
  43.      while(l<=h)
  44.      {
  45.           mid=(l+h)/2;
  46.           if(checkodd(mid)<=n)
  47.           {
  48.                ans=mid;
  49.                l=mid+1;
  50.           }
  51.           else
  52.           {
  53.               h=mid-1;
  54.           }
  55.      }
  56.      return ans;
  57. }
  58.  
  59. ll bsearchevn(ll n)
  60. {
  61.      ll l=0,h=999999999,mid;
  62.      ll ans=0;
  63.  
  64.      while(l<=h)
  65.      {
  66.           mid=(l+h)/2;
  67.           if(checkevn(mid)<=n)
  68.           {
  69.                ans=mid;
  70.                l=mid+1;
  71.           }
  72.           else
  73.           {
  74.               h=mid-1;
  75.           }
  76.      }
  77.      return ans;
  78. }
  79.  
  80. int main()
  81. {
  82.    ios_base::sync_with_stdio(0);
  83.    cin.tie(0);cout.tie(0);
  84.  
  85.  
  86.    test
  87.    {
  88.        ll n,m,i,j,ans;
  89.  
  90.  
  91.        cin>>i>>j;
  92.  
  93.        if(i>j) swap(i,j);
  94.  
  95.        n=bsearchevn(i-1)+bsearchodd(i-1);
  96.        m=bsearchevn(j)+bsearchodd(j);
  97.  
  98.        ans=m-n;
  99.  
  100.        if(i==0) ans++;
  101.  
  102.        cout<<"Case "<<cs<<": "<<ans<<endl;
  103.  
  104.    }
  105.  
  106.  
  107.    get_lost_idiot;
  108. }
  109.  
RAW Paste Data