fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cstring>
  5.  
  6. using namespace std;
  7. typedef long long int lld;
  8. lld n;
  9. string s;
  10. int odd, even;
  11.  
  12. lld dp[10][100][100][2];
  13.  
  14. lld solve(lld pos, lld evensum, lld oddsum, lld flag)
  15. {
  16.     lld &ans = dp[pos][evensum][oddsum][flag];
  17.     if (ans!=-1) return ans;
  18.     ans=0;
  19.     if (pos==n)
  20.     {
  21.         return (evensum-oddsum == 1);
  22.     }
  23.  
  24.     if (!flag)
  25.     {
  26.         for (int i=0; i<=9; i++)
  27.         {
  28.             if (pos%2==even)
  29.             {
  30.                 ans+=solve(pos+1, evensum+i, oddsum, 0);
  31.             }
  32.             else
  33.             {
  34.                 ans+=solve(pos+1, evensum, oddsum+i, 0);
  35.             }
  36.         }
  37.     }
  38.     else
  39.     {
  40.         int u = s[pos]-'0';
  41.         for (int i=0; i<u; i++)
  42.         {
  43.             if (pos%2==even)
  44.                 ans+=solve(pos+1, evensum+i, oddsum, 0);
  45.             else
  46.             {
  47.                 ans+=solve(pos+1, evensum, oddsum+i, 0);
  48.             } 
  49.         }
  50.         if (pos%2==even)
  51.             ans+=solve(pos+1, evensum+u, oddsum, 1);
  52.         else
  53.         {
  54.             ans+=solve(pos+1, evensum, oddsum+u, 1);
  55.         } 
  56.     }
  57.  
  58.     return ans;
  59. }
  60.  
  61. bool isGood()
  62. {
  63.     lld evensum, oddsum;
  64.     evensum=oddsum=0;
  65.     for (int i=0; i<n; i++)
  66.     {
  67.         if (i%2==odd)
  68.             oddsum+=s[i]-'0';
  69.         else
  70.         {
  71.             evensum+=s[i]-'0';
  72.         }
  73.  
  74.     }
  75.     return (evensum-oddsum==1);
  76. }
  77.  
  78. int main()
  79. {
  80.     lld t;
  81.     cin>>t;
  82.     while (t--)
  83.     {
  84.         string str1, str2;
  85.         cin>>str1>>str2;
  86.         s = str2;
  87.         n = s.size();
  88.         lld n1 = str1.size();
  89.         if (n1!=n)
  90.         {
  91.             for (lld i=n1; i<n; i++)
  92.                 str1 = "0"+str1;
  93.         }
  94.         if (n%2==1)
  95.         {
  96.             odd = 0;
  97.             even = 1;
  98.         }
  99.         else
  100.         {
  101.             odd = 1;
  102.             even = 0;
  103.         }
  104.         memset(dp, -1, sizeof(dp));
  105.         lld ans1 = solve(0, 0, 0, 1);
  106.         s = str1;
  107.         memset(dp, -1, sizeof(dp));
  108.         lld ans2 = solve(0, 0, 0, 1);
  109.         lld ans3 = isGood();
  110.         cout<<ans1-ans2+ans3<<endl;
  111.     }
  112.     return 0;
  113. }
Success #stdin #stdout 0s 4932KB
comments (?)
stdin
copy 
2
1 10
10 100
stdout
copy 
1
9
https://ideone.com/mZRp0n
language:
C++14 (gcc 8.3)
created:
4 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!