[Codeforces] D. Random Task

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D. Random Task
Source            : Codeforces
Category          : Dynamic Programing, Search
Algorithm         : Digit DP, Binary Search
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
#define ll            long long int  
  
ll dp[70][70];  
bool memoize[70][70];  
int a[70];  
  
ll m, k;  
  
ll solve(int pos, int one = 0, bool flag = 1, bool take = 0)  
{  
      if (pos < 0) return one == k;  
      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;  
}  
  
ll digit_dp(ll num)  
{  
      int len = 0;  
      while (num) a[len++] = num % 2, num /= 2;  
      return solve(len-1);  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(NULL);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> m >> k;  
      ll lo = 1;  
      ll hi = 1e18;  
      ll ans = -1;  
      while (lo <= hi)  
      {  
            ll mid = lo + (hi - lo) / 2;  
            ll cnt = digit_dp(mid*2) - digit_dp(mid);  
            if (cnt == m)  
            {  
                  ans = mid;  
                  hi = mid - 1;  
            }  
            else if (cnt < m) lo = mid + 1;  
            else hi = mid - 1;  
      }  
      assert(ans != -1);  
      cout << ans;  
}