fork download
copy 
  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][2];
  23. ll  calc(int ind,int re,string s){
  24. 	if(ind>s.length())
  25. 	return 1;
  26. 	int li;//limit of ith digit
  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 4524KB
comments (?)
stdin
copy 
3
5 15
120 125
779 783
stdout
copy 
Case #1: 6
Case #2: 3
Case #3: 2
https://ideone.com/CaIWB3
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!