#include "biscuits.h"
#include <cassert>
typedef long long int64_t;
// O(Q * K^2)-time solution
int64_t count_tastiness(int64_t numGroups, std::vector<int64_t> initialCount) {
while (initialCount.size() < 62) initialCount.push_back(0);
int64_t spareCount = 0;
auto numWays = std::vector<int64_t>{1};
for (int64_t i = 0; i < static_cast<int64_t>(initialCount.size()); ++i) {
if (initialCount[i] + spareCount >= numGroups) {
spareCount = spareCount + initialCount[i] - numGroups;
assert(spareCount >= 0);
numWays.push_back(numWays.back() * 2);
} else {
int64_t maxPossible = 0;
int64_t availableQty = 0;
for (int64_t j = 0; j <= i; ++j) {
availableQty += initialCount[j] << j;
}
int64_t borrowedQty = 0;
for (int64_t j = i; j >= 0; --j) {
assert(availableQty >= borrowedQty);
assert((borrowedQty % (1LL << j)) == 0);
int64_t curCount = initialCount[j];
int64_t returnedQty = std::min(borrowedQty, curCount << j);
curCount -= returnedQty >> j;
availableQty -= returnedQty;
borrowedQty -= returnedQty;
assert(curCount >= 0 && curCount <= initialCount[j]);
if (((availableQty - borrowedQty) >> j) >= numGroups) {
borrowedQty += numGroups << j;
borrowedQty = std::max(0LL, borrowedQty - (curCount << j));
maxPossible |= 1LL << j;
}
availableQty -= curCount << j;
}
assert(borrowedQty == 0);
int64_t curWays = 0;
for (int64_t j = 0; j < i + 1; ++j) {
if (((maxPossible + 1) & (1LL << j)) > 0) curWays += numWays[j];
}
numWays.push_back(curWays);
spareCount = 0;
}
spareCount >>= 1LL;
}
return numWays.back();
}
