fork download 
  1. #include<bits/stdc++.h>
  2. // #pragma GCC optimize("Ofast")
  3. // #pragma GCC target("avx,avx2,fma")
  4. // #pragma GCC optimization("unroll-loops")
  5. // #pragma GCC optimize("unroll-loops")
  6. // #pragma GCC optimize("fast-math")
  7. // #pragma GCC optimize("no-stack-protector")
  8. // #define ll __int128
  9. #define ll long long
  10. // #define ll int
  11. #define f(i,a,b) for(int i=a;i<b;i++)
  12. #define mod 1000000007
  13. // #define mod 1000000009 
  14. #define mp make_pair
  15. #define uniq(v) (v).erase(unique(all(v)),(v).end())
  16. #define ff first
  17. #define ss second
  18. #define rf(i,a,b) for(int i=a;i>=b;i--)
  19. #define sc(a) scanf("%lld",&a)
  20. #define pf printf
  21. #define sz(a) (int)(a.size())
  22. #define psf push_front
  23. #define ppf pop_front
  24. #define ppb pop_back
  25. #define pb push_back
  26. #define pq priority_queue
  27. #define all(s) s.begin(),s.end()
  28. #define sp(a) setprecision(a)
  29. #define rz resize
  30. #define ld long double
  31. #define inf (ll)1e18
  32. #define ub upper_bound
  33. #define lb lower_bound
  34. #define bs binary_search
  35. #define eb emplace_back
  36. const double pi = acos(-1);
  37. ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
  38. // ll binpow(ll a, ll b, ll md){ll res=1;a%=mod;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
  39.  
  40. using namespace std;
  41.  
  42. ll dp[11][101][101][2];
  43.  
  44. ll fn(int i, int tot, int other, int tight, string s)
  45. {
  46.     if(i>=sz(s))
  47.     {
  48.         if(other==tot && other>0 && tot>0)
  49.             return 1;
  50.         else
  51.             return 0;
  52.     }
  53.     ll &ans=dp[i][tot][other][tight];
  54.     if(ans==-1)
  55.     {
  56.         ans=0;
  57.         int mx=(tight?(s[i]-'0'):9);
  58.         f(j,0,mx+1)
  59.             ans+=(fn(i+1,tot,other+j,tight&&(j==mx),s)+fn(i+1,tot+j,other,tight&&(j==mx),s));
  60.     }
  61.     return ans;
  62. }
  63.  
  64. int main()
  65. {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(NULL);
  68.     // freopen("gift1.in","r",stdin);
  69.     // freopen("gift1.out","w",stdout);
  70. #ifndef ONLINE_JUDGE
  71.     freopen("input.txt","r",stdin);
  72.     freopen("output.txt","w",stdout);
  73. #endif
  74.     int z=1;
  75.     // cin>>z;
  76.     while(1)
  77.     { 
  78.         string a,b;
  79.         cin>>a>>b;
  80.         if(a=="0" && b=="0")
  81.             break;
  82.         memset(dp,-1,sizeof(dp));
  83.         ll R=fn(0,0,0,1,b)/2;
  84.         ll val=stoi(a)-1;
  85.         a=to_string(val);
  86.         memset(dp,-1,sizeof(dp));
  87.         ll L=fn(0,0,0,1,a)/2;
  88.         cout<<(R-L)<<"\n";
  89.         // cout<<a<<" "<<L<<" "<<b<<" "<<R<<"\n";
  90.     }    
  91. }
Success #stdin #stdout 0.01s 5552KB
comments (?)
stdin 
1 11
12 20
1 20
3 100
6354 234363
123456789 234567891
0 0
stdout 
1
0
1
18
244776
739137401
https://ideone.com/qw85QZ
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!