#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
long long count_tastiness(long long x, vector<long long> a) {//dp[i] = number of states such that the 2 ^ (i - 1) is the largest might be turned on bit
const int k = 61;
a.insert(a.begin(), 0LL);
while (a.size() < k) {
a.push_back(0);
}
vector<long long> b = a;
for (int i = 1; i < k; ++i) {
b[i] += b[i - 1] / 2;
}
vector<long long> dp(k);
dp[0] = 1;
for (int i = 1; i < k; ++i) {
if (b[i] < x) {
dp[i] = dp[i - 1];
continue;
}
dp[i] = dp[i - 1] + 1;
long long needed = max(0LL, x - a[i]) * 2;
for (int j = i - 1; j >= 1; --j) {
if (b[j] >= needed + x) {
dp[i] += dp[j - 1]; // if you don't turn on j
needed = max(0LL, needed + x - a[j]) * 2;
} else {
needed = max(0LL, needed - a[j]) * 2;
}
}
}
return dp[k - 1];
}
