fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // define
  5.  
  6. #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
  7. #define ll long long
  8. #define ii pair <int , int>
  9. #define iii pair <int , ii>
  10. #define se second
  11. #define fi first
  12. #define all(v) (v).begin() , (v).end()
  13. #define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin())
  14. #define bit(x,i) (((x) >> (i)) & 1LL)
  15. #define flip(x,i) ((x) ^ (1LL << (i)))
  16. #define ms(d,x) memset(d , x , sizeof(d))
  17. #define exist __exist
  18. #define ends __ends
  19. #define visit visited
  20. #define left __left
  21. #define right __right
  22. #define sitingfake 1
  23. #define orz 1
  24. //constant
  25.  
  26. const long long mod = 1e9 + 7;
  27. const long long linf = 4557430888798830399LL;
  28. const long long nlinf = -4485090715960753727LL;
  29. const int inf = 1061109567;
  30. const int ninf = -1044266559;
  31. const int dx[] = {0 , -1 , 0 , 1};
  32. const int dy[] = {-1 , 0 , 1 , 0};
  33.  
  34. template<typename T> bool maximize(T &a, const T &b)
  35. {
  36.     if(a < b) {a = b; return 1;}
  37.     return 0;
  38. }
  39.  
  40. template<typename T> bool minimize(T &a, const T &b)
  41. {
  42.     if(a > b) {a = b; return 1;}
  43.     return 0;
  44. }
  45.  
  46. void Plus(ll & a ,ll b)
  47. {
  48.     b %= mod;
  49.     a += b;
  50.     if(a < 0) a += mod;
  51.     a %= mod;
  52.     return;
  53. }
  54.  
  55. void Mul(ll & a, ll b)
  56. {
  57.     (a *= (b % mod)) %= mod;
  58.     return;
  59. }
  60.  
  61. //code
  62.  
  63. ll L , R;
  64.  
  65. ll n , k;
  66.  
  67. ll dp[20][20][2][2];
  68.  
  69. int a[20];
  70.  
  71. int tag = 0;
  72.  
  73. ll compute(int curnum , bool lim , bool zero , int numdigits , int rem)
  74. {
  75.     if(curnum == 0)
  76.     {
  77.         if(rem == (k & 1LL))
  78.         {
  79.             return numdigits;
  80.         }
  81.         return 0;
  82.     }
  83.     else
  84.     {
  85.         if(!lim && dp[curnum][numdigits][rem][zero] != -1)
  86.         {
  87.             return dp[curnum][numdigits][rem][zero];
  88.         }
  89.         int C = lim ? a[curnum] : 9;
  90.         ll ans = 0;
  91.         if(zero)
  92.         {
  93.             ans += compute(curnum - 1, 0 , 1 , 0 , 0);
  94.         }
  95.         else
  96.         {
  97.             ans += compute(curnum - 1 , (lim && C == 0) , 0 , numdigits + (tag == 0) , ((rem * 10) % 2));
  98.         }
  99.  
  100.         for(int c = 1; c <= C; c++)
  101.         {
  102.             ans += compute(curnum - 1, (lim && C == c) , 0 , numdigits + (tag == c) , ((rem * 10) + c) % 2);
  103.         }
  104.         if(!lim) dp[curnum][numdigits][rem][zero] = ans;
  105.         return ans;
  106.     }
  107. }
  108.  
  109. ll calc(ll x)
  110. {
  111.     int cnt = 0;
  112.     while(x != 0)
  113.     {
  114.         a[++cnt] = x % 10;
  115.         x /= 10;
  116.     }
  117.     return compute(cnt , 1 , 1 , 0 , 0);
  118. }
  119. void solve(void)
  120. {
  121.     cin >> k >> n;
  122.     L = k;
  123.     R = k + 2LL *(n - 1);
  124.     for(int i = 0; i <= 9; i++)
  125.     {
  126.         tag = i;
  127.         ms(dp , -1);
  128.         cout << calc(R) - calc(L - 1) << " ";
  129.     }
  130. }
  131. /**
  132. **/
  133. signed main()
  134. {
  135.    ios_base::sync_with_stdio(0);
  136.    cin.tie(0);
  137.    cout.tie(0);
  138.  
  139.    #define task "houses"
  140.  
  141.    if(fopen(task".inp","r"))
  142.    {
  143.        freopen(task".inp","r",stdin);
  144.        freopen(task".out","w",stdout);
  145.    }
  146.  
  147.    int tc = 1;
  148. //   cin >> tc;
  149.    while(tc--) solve();
  150.  
  151. //   execute;
  152. }
  153.  
  154.  
  155.  
  156.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0 0 0 0 0 0 0 0 0
https://ideone.com/apODQf
language:
C++14 (clang 8.0)
created:
6 hours ago
visibility:
public

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!