Candice's trip to the candy shop

In Python 3.4:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Candide_ = {}

def Candide(n, depth):
    "Candice's trip to the candy shop"
    if depth == 0:
        res = 1 if n == 0 else 0
    elif n == 0:
        res  = 1
    elif (n, depth) in Candide_:
       res  =  Candide_[(n, depth)]
    else:
        res = sum(Candide(m, depth - 1) for m in [n-1, n-2, n-5, n-10] if m >= 0)
        Candide_[(n, depth)] = res
    return res

print(Candide(40, 10))

Here is an efficient Dynamic Programming solution. Let $N(c,d)$ denote the number of ways of buying exactly $c$ candies with exactly $d$ dollars. Also denote the prices of the candies by $p_i, i=1,2,3,4$ . Then we have the following recursion $N(c,d)=\sum_{i=1}^{4}N(c-1,d-p_i)$ with the convention that $N(a,b)=0$ if $b\leq 0$ . We have the initial condition that $N(1,p_i)=1, \forall i$ and $N(1,k)=0$ otherwise. This fully specifies the recursion. We are interested in the quantity $\sum_{i=1}^{10}N(i,40)$ .

Complexity for $c$ candies and a total of $d$ dollars is $\Theta(cd)$ .

2-D DP code in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <bits/stdc++.h>
using namespace std;

int dp[100][20];

int f(int N, int choco)
{
    if(N < 0 || choco < 0)
        return 0;
    if(N == 0)
        return 1;
    if(dp[N][choco] != -1)
        return dp[N][choco];

    return dp[N][choco] = f(N-1, choco - 1) + f(N-2, choco - 1) + f(N-5, choco - 1) + f(N-10, choco - 1);
}

int main() 
{
    memset(dp, -1, sizeof(dp));
    cout << f(40, 10) << endl;
    return 0;
}

**The whole issue here was solving the equation a+2b+5c+10d=40, where constraints were all of them have to be integers and 0<a+b+c+d<11. Now to account for the different arrangements , one solution will give (a+b+c+d)!/(a!b!c!d!) different arrangements. Due to being a layabout, I did it in R instead of C++.)

Python 3.4:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

candy_costs = (1, 2, 5, 10)
cost_limit = 40
def children(candy):
    cost = sum(candy)
    candies = len(candy)
    if candies < 10:
        for candy_cost in candy_costs:
            if cost + candy_cost <= cost_limit:
                yield candy + (candy_cost,)
ways = 0
start = ()
level = {0: [start]}
current_level = 0
while level[current_level]:
    current_level += 1
    level[current_level] = []
    for candy in level[current_level - 1]:
        for child in children(candy):
            if sum(child) == 40:
                ways += 1
            level[current_level].append(child)
print ("Answer:", ways)

One way would be to calculate the sum of coefficients of $x^{40}$ in the expansion of $(x+x^2+x^5+x^{10})^n$ where $1 \leq n \leq 10$ . We can further simplify calculations by noticing that there are no possible combinations below a combination of 4 candies since the costliest is worth $\$10$ .The only one of 4 in total is $4$ candies of $\$10$ each.

So essentially, you would need to calculate only for $5 \leq n \leq 10$ and add 1 to the final answer, giving $44662$ .

Alternatively, you can calculate the sets of $A^n$ where $A=\{1,2,5,10 \}$ and examine exactly how many of these add up to a total of $40$ . Here as well, you can limit your calculations to $5 \leq n \leq 10$ and add 1 to the total. You would arrive at the same answer.

Other approaches are more than welcome, and you are encouraged to post your code even if you used this very same method.

This solution maintains a table c[n][d], indicating in how many ways n candies can be bought for $d.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

        int c[][] = new int[11][41];
        int candy[] = { 1, 2, 5, 10 };

        for (int i = 0; i <= 40; i++)
            for (int j = 0; j <= 10; j++) c[j][i] = 0;

        c[0][0] = 1;

        for (int j = 1; j <= 10; j++) {
            for (int i = 0; i <= 40; i++) if (c[j-1][i] > 0)
                for (int k = 0; k < 4; k++) {
                    int new_i = i + candy[k];
                    if (new_i <= 40) c[j][new_i] += c[j-1][i];
                }
            }            

        int sum = 0;
        for (int j = 1; j <= 10; j++) sum += c[j][40];
        out.println(sum);

I also took the challenge listed below: What will be the solution if Candide received $400 and could buy up to 100 candies? My code gives 9.549933817559471E57 within a fraction of a second.