fork(1) download
  1. #include<bits/stdc++.h>
  2. #include<iomanip>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. #define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
  6. #define ar array
  7. #define all(a) a.begin(),a.end()
  8. #define Unique(a) a.erase(unique(all(a)), a.end())
  9. #define mod 998244353
  10. #define ld long double
  11. #define endl "\n"
  12. #define wh(x) cerr<< #x << " is " << x << '\n';
  13. #define pb push_back
  14. #define mxn 2005
  15. #define fi first
  16. #define se second
  17. #define inf 1e9
  18. using namespace __gnu_pbds;
  19. using namespace std;
  20. typedef long long int ll;
  21. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ord_set;
  22. ll dp[20][10];
  23. ll calc(int ind,int re,string s){
  24. if(ind>s.length())
  25. return 1;
  26. int li;
  27. ll ans=dp[ind][re];
  28. if(ans>=0)
  29. return ans;
  30. ans=0;
  31. if(re){
  32. li=s[ind-1]-'0';
  33. if(ind&1){
  34. for(int i=0;i<=li;i++){
  35. if(i&1){
  36. if(i<li)
  37. ans+=calc(ind+1,0,s);
  38. else
  39. ans+=calc(ind+1,1,s);
  40. }
  41. }
  42. }
  43. else{
  44. for(int i=0;i<=li;i++){
  45. if(i%2==0){
  46. if(i<li)
  47. ans+=calc(ind+1,0,s);
  48. else
  49. ans+=calc(ind+1,1,s);
  50. }
  51. }
  52. }
  53. }
  54. else{
  55. li=9;
  56. if(ind&1){
  57. for(int i=0;i<=li;i++){
  58. if(i&1)
  59. ans+=calc(ind+1,0,s);
  60. }
  61. }
  62. else{
  63. for(int i=0;i<=li;i++){
  64. if(i%2==0)
  65. ans+=calc(ind+1,0,s);
  66. }
  67. }
  68. }
  69. return dp[ind][re]=ans;
  70. }
  71. ll solve(){
  72. string l,r;
  73. cin>>l>>r;
  74. ll l1=0;
  75. for(int i=0;i<l.length();i++)
  76. l1*=10,l1+=l[i]-'0';
  77. --l1;
  78. string nl=to_string(l1);
  79. ll a=0,b=0;
  80. memset(dp,-1,sizeof dp);
  81. for(int i=0;i<nl.length();i++)
  82. a+=calc(i+1,i==0,nl);
  83. memset(dp,-1,sizeof dp);
  84. for(int i=0;i<r.length();i++)
  85. b+=calc(i+1,i==0,r);
  86. return b-a;
  87. }
  88. int main(void){
  89. fast;
  90. int t;
  91. cin>>t;
  92. for(int i=1;i<=t;i++)
  93. cout<<"Case #"<<i<<": "<<solve()<<endl;
  94. }
  95.  
Success #stdin #stdout 0s 4352KB
stdin
3
5 15
120 125
779 783

stdout
Case #1: 6
Case #2: 3
Case #3: 2