#include "biscuits.h"
//#include"grader.cpp"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
vector<ll> ct, v, ub;
ll solve(int id, ll carry, ll x){
if(id == -1)
return 1;
if(ub[id] < carry)
return 1;
ll minus = min(v[id], carry);
carry-=minus;
ll ret = solve(id-1,carry*2,x);
// cerr << id << ' ' << carry << ' ' << x << endl;
// cerr << "->" << carry+x << ' ' << ct[id] << ' ' << minus << endl;
if(carry+x <= ct[id]-minus)
ret += solve(id-1, (max(0ll, x+carry+minus-v[id]))*2, x);
return ret;
}
bool solvetest(int id, ll carry, ll x){
if(id == -1)
return false;
ll minus = min(v[id], carry);
carry-=minus;
ll ret = solve(id-1,carry*2,x);
if(carry+x <= ct[id]-minus)
return true;
return ret;
}
void bsearch(int id, ll x){
ll ini = -1, fim = 1000000000000000000;
// cerr << id << ' ' <<fim << endl;
while(ini!=fim){
// cerr << ini << ' ' << fim << '\n';
ll m = (ini+fim+1)>>1;
if(solvetest(id,m,x))
ini = m;
else fim = m-1;
}
ub[id] = ini;
}
long long count_tastiness(long long x, std::vector<long long> a) {
a.resize(60,0);
ct = v = a;
int k = a.size();
for(int i = 1; i < k; i++){
ct[i]+=ct[i-1]/2;
}
ub.resize(60);
for(int i = 0; i < k; i++)
bsearch(i,x);
return solve(k-1,0,x);
}
