fork(4) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. string str;
  6.  
  7. int dp[10][10][2][100][100];
  8. int numDig;
  9.  
  10. int solve(int idx, int realidx, int tight, int e, int o){
  11.     if(idx == numDig){
  12.         return realidx % 2 ? ((e-o)==1 ? 1 : 0) : ((o-e) == 1 ? 1 : 0);
  13.     }
  14.     if(dp[idx][realidx][tight][e][o] != -1)
  15.         return dp[idx][realidx][tight][e][o];
  16.     int ans = 0;
  17.     if(tight){
  18.         for(int i=0; i<str[idx]-'0'; i++){
  19.             int newRealidx = (realidx || (i!=0))?realidx+1:0;
  20.             int newo = newRealidx == 0 ? 0 : ((newRealidx)%2 ? o+i: o);
  21.             int newe = newRealidx == 0 ? 0 : ((newRealidx)%2 ?  e : e+i);
  22.             ans += solve(idx+1, newRealidx, 0, newe, newo);
  23.         }
  24.         int newRealidx = (realidx>0 || (str[idx]-'0' !=0))?realidx+1:0;
  25.         int newo = newRealidx == 0 ? 0 : ((newRealidx)%2 ? o+str[idx]-'0' : o);
  26.         int newe = newRealidx == 0 ? 0 : ((newRealidx)%2 ?  e : e+str[idx]-'0');
  27.         ans += solve(idx+1, newRealidx, 1, newe, newo);
  28.     } else {
  29.         for(int i=0; i<=9; i++){
  30.             int newRealidx = (realidx || (i!=0))?realidx+1:0;
  31.             int newo = newRealidx == 0 ? 0 : ((newRealidx)%2 ?  o+i : o);
  32.             int newe = newRealidx == 0 ? 0 : ((newRealidx)%2 ?  e : e+i);
  33.             ans += solve(idx+1, newRealidx, 0, newe, newo);
  34.         }
  35.     }
  36.     return dp[idx][realidx][tight][e][o] = ans;
  37. }
  38.  
  39. int main(){
  40.     int t;
  41.     scanf("%d",&t);
  42.     while(t--){
  43.         int a, b;
  44.         int ans = 0;
  45.         scanf("%d%d",&a,&b);
  46.         a--;
  47.         if(b>0){
  48.             str = to_string(b);
  49.             numDig = str.size();
  50.             memset(dp, -1, sizeof dp);
  51.             ans = solve(0, 0, 1, 0, 0);
  52.             //printf("ub : %d\n",ans);
  53.         }
  54.         if(a>0){
  55.             str = to_string(a);
  56.             numDig = str.size();
  57.             memset(dp, -1, sizeof dp);
  58.             ans -= solve(0, 0, 1, 0, 0);
  59.         }
  60.         printf("%d\n",ans);
  61.     }
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0s 23880KB
comments (?)
stdin
copy 
2
1 10
10 100
stdout
copy 
1
9
https://ideone.com/hHgnXd
language:
C++14 (gcc 8.3)
created:
6 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!