fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dp[10][2][50][50];
  5.  
  6. string toString(int num){
  7. 	stringstream ss;
  8.    	ss << num;
  9.    	return ss.str();
  10. 	}
  11.  
  12. int digdp(int index, int isEqual, int es, int os, string num, int limit){
  13. 	int &res = dp[index][isEqual][es][os];
  14. 	if(res==-1){
  15. 		res=0;
  16. 		if(index==limit){
  17. 			if(!isEqual && (es-os)==1){res=1;cout<<"("<<es<<" "<<os<<") ";}
  18. 		}
  19. 		else{
  20. 			if(isEqual){
  21. 				for(int i=0; i<=num[index]-'0'; i++){
  22. 					if(i==num[index]-'0'){
  23. 						res += digdp(index+1, 1, (index%2)?es:es+i, (index%2)?os+i:os, num, limit);
  24. 					}
  25. 					else{
  26. 						res += digdp(index+1, 0, (index%2)?es:es+i, (index%2)?os+i:os, num, limit);
  27. 					}
  28. 				}
  29. 			}
  30. 			else{
  31. 				for(int i=0; i<=9; i++){
  32. 					res += digdp(index+1, 0, (index%2)?es:es+i, (index%2)?os+i:os, num, limit);
  33. 				}
  34. 			}
  35. 		}
  36. 	}
  37. 	return res;
  38. }
  39.  
  40. int solve(int n){
  41. 	if(n<10)return 0;
  42. 	int ret = 0;
  43. 	string num = toString(n);
  44. 	for(int i=1; i<=num[0]-'0'; i++){
  45. 		ret += digdp(0,1,0,0,num,num.length());
  46. 	}
  47. 	return ret;
  48. 	}
  49.  
  50. int main() {
  51. 	int t;
  52. 	scanf("%d",&t);
  53. 	while(t--){
  54. 		int a,b;
  55. 		cin>>a>>b;
  56. 		memset(dp,-1,sizeof(dp));
  57. 		a = solve(a);
  58. 		memset(dp,-1,sizeof(dp));
  59. 		b = solve(++b);
  60. 		cout<<b-a<<endl;
  61. 	}
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 15440KB
comments (?)
stdin
copy 
2
1 10
10 100
stdout
copy 
(1 0) 1
(1 0) (2 1) (3 2) (4 3) (5 4) (6 5) (7 6) (8 7) (9 8) 10
https://ideone.com/N1VV4O
language:
C++14 (gcc 8.3)
created:
6 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!