need help in Nested Candy Boxes problem:

general
, , ,
1

Hi!!
I tried solving this problem and for some random test cases it worked fine but, it is giving me a wrong answer when submitted.
can anyone tell me where did i go wrong…

#define ll long long  
int main()   
{  
    ll t=0,p=0;  
	cin>>p>>t;  
	ll a[p],i=0;  
	while(p--)  
	    cin>>a[i++];  
	while(t--)  
	{  
	    ll q=0,val=0,n1=0;  
	    cin>>q;  
	    n1=q;  
	    for(ll i=n-1;i>=0;i--)  
	    {  
	        val=val+(ceil((long double)n1/a[i]));  
	        n1=(ceil((long double)n1/a[i]));  
	    }  
	    cout<< val;  
	}  
	return 0;  
}
2

You might find my unofficial editorial useful https://discuss.codechef.com/questions/133310/unpacking-amboxes

3

@joffan thanks for the link it was useful, i think I used the same approach as your’s (feeding boxes to levels) and it didn’t work,

4
  1. If you preprocess your a array so that it holds (net) candies per box rather than boxes per box, you will only need to do one operation per level.
  2. You can see that for non-zero candies we need to open at least one box for every level. So start with that n value, subtract one candy from the query quantity and use floor instead of ceil - effectively asking how many candies to open the next box at each level.
  3. Once you have these two in place, you can break out of the summation loop once the net candies/box exceeds q, saving a lot of time for deep nestings
  4. Finally if needed you can implement the “wrapper” consideration during preprocessing that I mention in my unofficial editorial
5

Thanks for the help, I will try it out…