[UVa] 12208 - How Many Ones Needed?

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12208 - How Many Ones Needed?
Source            : UVA Online Judge
Category          : Dynamic Programing
Algorithm         : Digit DP
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll            long long int  
  
ll dp[40][40];  
bool memoize[40][40];  
int a[40];  
  
inline ll solve(int pos, int one = 0, bool flag = 1, bool take = 0)  
{  
      if (pos < 0) return one;  
      ll &ret = dp[pos][one];  
      bool &mem = memoize[pos][one];  
      if (!flag && take && mem) return ret;  
      int loop = 1;  
      if (flag) loop = a[pos];  
      ll sum = 0;  
      for (int i = 0; i <= loop; i++)  
      {  
            if (!take && i == 0) sum += solve(pos-1, 0, 0, 0);  
            else sum += solve(pos-1, one + i, flag & i == a[pos], 1);  
      }  
      if (!flag && take) mem = 1, ret = sum;  
      return sum;  
}  
  
inline ll digitDP(ll num)  
{  
      if (num <= 0) return 0;  
      int len = 0;  
      while (num) a[len++] = num % 2, num /= 2;  
      return solve(len-1);  
}  
  
int main()  
{  
      ll a, b;  
      int tcase = 1;  
      while (cin >> a >> b)  
      {  
            if (a == 0 && b == 0) break;  
            if (a > b) swap(a, b);  
            ll tone = digitDP(b) - digitDP(a-1);  
            cout << "Case " << tcase++ << ": " << tone << endl;  
      }  
}