#include "biscuits.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define cout cerr
const int JFF = 300000;
int flog(int x) {
//MSB of x
int ct=0;
while (x>1) {
x>>=1;
ct++;
}
return ct;
}
int X;
vector<int> A;
map<pair<int,int>,int> cache;
int solve(int mval, int index) {
//index is the last relevant index
//consider that we take this bit
//then how much do we need from lower bits
//and thus what is the max we can take from lower bits as well
//if we don't take the bit, just round down to the power of 2
if (index==-1) {
return mval>=0;
}
if (mval<0) {
return 0;
}
if (cache.count({mval,index})) {
return cache[{mval,index}];
}
if (mval<(1LL<<index)) {
return cache[{mval,index}] = solve(mval,index-1);
}
int s1 = solve((1LL<<index)-1,index-1);
//we take this bit
int req = X;
int ava = A[index];
int k;
if (ava>=req) {
//take bit for free
k=(1LL<<index)-1;
}
else {
//req>ava
int rem = req-ava; //need to fundraise from smaller powers
int reqsum = rem*(1LL<<index);
int actualsum = 0;
for (int i=0; i<index; i++) {
actualsum+=(1LL<<i)*A[i];
}
if (actualsum<reqsum) {
k=-1; //no sol
}
else {
int rem_for_prev_indices = actualsum-reqsum;
k = rem_for_prev_indices/X;
}
//assert(k<=((1LL<<fl)-1));
k=min(k,((1LL<<index)-1));
cout << "DOING " << mval <<" " << index <<" " << req<<" " << reqsum <<" " << actualsum <<" " << endl;
}
int s2 = solve(k,index-1);
cout << "CHOSEN" <<" " << mval <<" " << index <<" " << k << endl;
cout << "answered " << mval <<" " << index <<" " << s1 <<" " << s2 << " " << s1+s2 << endl;
return cache[{mval,index}] = s1+s2;
}
long long count_tastiness(long long x, std::vector<long long> a) {
cout << "STARTING NEW TEST CASE" << endl;
cache.clear();
while (a.size()<62) {
a.push_back(0);
}
A = a;
X = x;
int le = ((int)a.size())-1;
int ans = solve(((1LL<<(le+1))-1), le);
return ans;
}
