fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #define LL long long
  6. using namespace std;
  7.  
  8. bool mem[55][1055];
  9. LL dp[55][1055];
  10. LL f(int dig,int sum)
  11. {
  12.     if(dig==0)
  13.         return (sum==500);
  14.     if(mem[dig][sum])
  15.         return dp[dig][sum];
  16.     mem[dig][sum]=1;
  17.     LL ret=0LL;
  18.     for(int i=0;i<=9;++i)
  19.     {
  20.         if(dig%2)
  21.         ret+=f(dig-1,sum+i);
  22.         else
  23.         ret+=f(dig-1,sum-i);
  24.     }
  25.     dp[dig][sum]=ret;
  26.     return ret;
  27. }
  28.  
  29. LL solve(string x)
  30. {
  31.     LL ret=0;
  32.     int len=x.size();
  33.     int sum=501;int qued=len;
  34.     for(int i=0;i<len;++i)
  35.     {
  36.         qued--;
  37.         int d=x[i]-'0';
  38.         for(int j=0;j<d;++j)
  39.         {
  40.             if(qued%2)
  41.             ret+=(f(qued,sum+j));
  42.             else
  43.             ret+=(f(qued,sum-j));
  44.         }
  45.         if(qued%2)
  46.         sum+=d;
  47.         else
  48.         sum-=d;
  49.     }
  50.  
  51.     return ret;
  52. }
  53.  
  54.  
  55. int main()
  56. {
  57.   string a,b;cin>>b>>a;
  58.  
  59.    vector<int> tmp;
  60.    for(int i=0;i<a.size();++i)
  61.    {
  62.        tmp.push_back(a[i]-'0');
  63.    }
  64.    reverse(tmp.begin(),tmp.end());
  65.    for(int i=0;i<tmp.size();++i)
  66.    {
  67.        if(tmp[i]<9)
  68.        {
  69.            tmp[i]++;break;
  70.        }
  71.        else
  72.        {
  73.            tmp[i]=0;
  74.        }
  75.    }
  76.    if(tmp[tmp.size()-1]==0)tmp.push_back(1);
  77.     reverse(tmp.begin(),tmp.end());
  78.    vector<char> t;
  79.    for(int i=0;i<tmp.size();++i)
  80.    {
  81.        t.push_back((char)(48+tmp[i]));
  82.    }
  83.    string s(t.begin(),t.end());
  84.    //cout<<s<<endl;
  85.    cout<<solve(s)-solve(b)<<endl;
  86.    return 0;
  87. }
  88.  
Success #stdin #stdout 0s 3988KB
comments (?)
stdin
copy 
10 100
stdout
copy 
10
https://ideone.com/5CemTn
language:
C++ (gcc 8.3)
created:
9 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!