1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
|
#include <bits/stdc++.h> #define Go(i , x , y) for(register int i = x; i <= y; i++) #define God(i , y , x) for(register int i = y; i >= x; i--) typedef long long LL; template < typename T > void sc(T& t) { char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();} while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x; } template < typename T , typename... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);}
LL dp[20][11] , d[20];
LL f(LL i , LL j) { if(dp[i][j] != -1) return dp[i][j]; if(!i) return dp[i][j] = 1; else { LL ans = 0; Go(digit , 0 , 9) if(digit != 4 && !(j == 6 && digit == 2)) ans += f(i-1 , digit); return dp[i][j] = ans; } }
LL calc(LL x) { int m = 0; while(x) { d[m++] = x%10; x/=10; } LL ans = 0; Go(i , 1 , m-1) { Go(j , 1 , 9) if(j != 4) ans += f(i-1 , j); }
int last = 0; God(i , m-1 , 0) { Go(j , (i == m-1) ? 1 : 0 , d[i]-1) if(j != 4 && !(last == 6 && j == 2)) ans += f(i , j); if(d[i] == 4) break; if(last == 6 && d[i] == 2) break; last = d[i]; } return ans; } int main() { memset(dp , -1 , sizeof(dp)); LL l , r; while(1) { sc(l , r); if(!l && !r) return 0; std::cout << calc(r+1) - calc(l) << std::endl; } return 0; }
|