fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3.  
  4.  
  5. #define ll long long 
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define fir first 
  8. #define sec second 
  9. #define piint pair < int , int >
  10. #define FOR( i , a , b ) for (int i = (a) , _b = (b) ; i <= _b ; i ++ )  
  11. #define pb push_back 
  12. #define str string 
  13. #define ALL(a) (a).begin() , (a).end() 
  14. #define rep( i , a , b) for (int i = (a) ; i < (b) ; i ++ )
  15. #define ld long double
  16. const int maxn = 1e3;
  17. #define debug 0
  18. #define oo (ll)(1e18)
  19.  
  20. ll dp[23][2][2]['z' + 3 ]['z' +3  ] ;
  21. str A , B ;
  22.  
  23.  
  24. ll dfs ( int i , bool ok_l , bool ok_r , int x , int y , int len ){
  25.  
  26. 	if ( i == len ) return 1 ;
  27. 	if (dp[i][ok_l][ok_r][x][y] != -1){
  28. 		return dp[i][ok_l][ok_r][x][y] ;
  29. 	}
  30.  
  31. 	char low = ok_l ? ( '0' ) : A[i] ;
  32. 	char high = ok_r ? ('9') : B[i] ;
  33. 	low = max ( ( i == 0 )? '1' : '0' , low );
  34. 	ll res = 0 ;
  35. 	FOR ( c , low , high ) {
  36.  
  37.  
  38. 		if ( i > 0 && c == y ) continue ;
  39. 		if ( i > 1 && c == x ) continue ;
  40. 		res += dfs ( i + 1 , ok_l | ( c > A[i]) , ok_r | ( c < B[i]) , y , c , len ) ; 
  41. 	}
  42. 	return dp[i][ok_l][ok_r][x][y] = res ;
  43.  
  44. 	// if ( i > )
  45. }
  46.  
  47. void input(){
  48.  
  49. 	ll a , b ; cin >> a >> b ;
  50.  
  51. 	A = to_string ( a ) ;
  52. 	B = to_string ( b ) ;
  53. 	str OLD = A ;
  54. 	ll ans = 0 ;
  55.  
  56. 	FOR ( len , A.size() , B.size()){
  57. 		memset ( dp , -1 , sizeof(dp)) ;
  58. 		A = OLD ;
  59.  
  60. 		while ( A.size() < len ) {
  61.  
  62. 			A = '0' + A ;
  63.  
  64. 		}
  65. 		if ( len < B.size())  ans += dfs ( 0 , 0 , 1 , 1 , 1 , len ) ;
  66. 		else ans += dfs ( 0 , 0 , 0 , 1 , 1 , len ) ;
  67. 	}
  68. 	cout << ans ;
  69.  
  70. }
  71. #define name "TASK" 
  72. int main(){
  73.     fast 
  74.     if(fopen(name".INP","r")) {
  75.         freopen (name".INP","r",stdin);
  76.         freopen (name".OUT","w",stdout);
  77.     }
  78.     input() ;
  79.     cerr << "\nTIME: = " << (1.0*clock())/CLOCKS_PER_SEC << '\n';
  80.     return(0) ;
  81. }
Success #stdin #stdout #stderr 0.01s 15120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
TIME: = 0.00599
https://ideone.com/ghjDRY
language:
C++14 (gcc 8.3)
created:
1 day 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!