/**
* 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
* ...
*
* Time Complexity: (unknown yet)
* Implementation 0.9 (Just for testing correctness)
*/
#include <bits/stdc++.h>
#include "biscuits.h"
typedef long long ll;
ll search(ll x, std::vector<ll> a) {
if (a.size() == 1)
return a[0] / x + 1;
ll zeroes = a[0], total = 0;
if (zeroes >= x) {
std::vector<ll> new_a = a;
new_a.erase(new_a.begin());
new_a[0] += (zeroes - x) / 2;
total += search(x, new_a);
}
a.erase(a.begin());
a[0] += zeroes / 2;
total += search(x, a);
return total;
}
ll count_tastiness(ll x, std::vector<ll> a) {
return search(x, a);
}
