/**
* Binary. Hmm, interesting. I started with [S2], which I solved with recursion in
* O(kq). The basic idea is to treat two 2^i biscuits in the bag as one 2^(i+1).
*
* A few greedy observations:
* (1) Given x, can we determine if it's possible? Well, we can simply iterate i
* from large to small. If the additional tastiness x we still need for a
* certain bag satisfies x >= 2^i, put a biscuit 2^i in the bag if there's one.
* (2) Biscuits of the same type can be distributed as evenly as possible, i.e.
* there is an optimal partition s.t. for every i
* |#2^i_biscuits_in_bag_1 - #2^i_biscuits_in_big_2| <= 1.
* (3) Unlike (1), (2), we consider from small to large. If x is odd, each bag needs
* at least 1 2^0 biscuit. After that, every 2 2^O biscuits can be grouped to
* form 1 2^1 biscuit, so we can add this num to the original num of 2^1
* biscuits. Well, let's write this recursively:
* def find():
* total = 0
* if #2^0 >= x:
* add floor((#2^0 - x) / 2) to #2^1 and recurse downdwards
* add floor(#2^0 / 2) to 2^1 and recurse downwards
* ...
*
* Can we AC this problem with (3)? I guess that the num of configurations given to
* find() isn't too many, so we can optimize it with memoization. Indeed, we can
* prove that in each level of find(), the num. of unique calls the next level of
* find() is bounded by x. This is because x >= x/2 + x/4 + x/8 + x/16 + .... [S1-3]
* are solved.
*
* In impl1, the function search(p, first) doesn't decrease as first increases.
* Furthermore, if search(p, w) and search(p, z) are both called, |w-z| <= x.
*
* Time Complexity: O(xqk * log(xk)) (partial solution)
* Implementation 1 (Only solves [S1-3], may solve [S4])
*/
#include <bits/stdc++.h>
#include "biscuits.h"
typedef long long ll;
ll x;
std::vector<ll> a;
struct pair_t {
int p;
ll first;
};
inline bool operator<(const pair_t& p1, const pair_t& p2) {
return p1.p < p2.p || (p1.p == p2.p && p1.first < p2.first);
}
std::map<pair_t, ll> cache;
inline ll search(int p, ll first) {
if (cache.find(pair_t{p, first}) == cache.end()) {
int k = a.size();
if (p == k - 1)
return first / x + 1;
ll total = search(p + 1, a[p + 1] + first / 2);
if (first >= x)
total += search(p + 1, a[p + 1] + (first - x) / 2);
cache[pair_t{p, first}] = total;
}
return cache[pair_t{p, first}];
}
ll count_tastiness(ll _x, std::vector<ll> _a) {
cache.clear();
x = _x, a = _a;
return search(0, a[0]);
}
