- Prepare
- Algorithms
- Implementation
- Chocolate Feast
- Discussions

# Chocolate Feast

# Chocolate Feast

+ 31 comments # Only 1 output worng among all cases?

Case No. 5, input string is "43203 60 5", my output is "892", right answer is "899" I just want to make sure whether there is a mistake at your end. Kindly check, I've checked plenty of time, If not Kindly explain the case? Much appreciaited.

+ 11 comments I've found out that there is a direct solution (i didn't get it myself, I just found out by searching, I solved the problem with while bucle like almost everybody).

### Code

`money = 10 cost = 2 extra = 2 boughtCandies = money / cost result = boughtCandies + (boughtCandies - 1) / (extra - 1)`

Does anyone know the math basis or where this comes from, or where can I read about this?

Thanks!

+ 2 comments Very simple. 100% all test cases passed

static int chocolateFeast(int n, int c, int m) { int wrapper=0; wrapper=n/c; int choc_count=wrapper; while(wrapper>=m) { wrapper=wrapper-m;//exchange wrapper++;//new choc wrapper.. so ++ choc_count++;//increase choc count } return choc_count; }

+ 2 comments The test case: 12 4 4 result is 3.

Why can't I borrow a Wrapper and when I finish mine, I return the Wrapper?

+ 2 comments I came up with a nice formula for solving the problem.

We start off with a self-referential formula:

`t = money + wrappers t = floor(n/c) + floor((t-1)/m)`

The reason we use

`t-1`

over`t`

is because the wrapper you acquire from your last exchanged chocolate is not part of your available resources.We then solve for t:

`t - floor((t - 1) / m) = floor(n/c) ceil(t - (t - 1) / m) = floor(n/c) ceil((mt - t + 1) / m) = floor(n/c)`

We can convert this to an inequality. The idea is that

`mt - t + 1`

must be at between`floor(n/c)-1`

(non-inclusive) and`floor(n/c)`

(inclusive) multiples of`m`

.`m(floor(n/c) - 1) < t(m - 1) + 1 <= m(floor(n/c)) m(floor(n/c) - 1) - 1 < t(m - 1) <= m(floor(n/c)) - 1 (m(floor(n/c) - 1) - 1) / (m - 1) < t <= (m(floor(n/c)) - 1 ) / (m - 1)`

Note there can be multiple values of

`t`

that are within this range. We select the largest, because we want the maximum amount of chocolates`t = floor((m * floor(n/c) - 1) / (m - 1))`

Another form of this is what @ansonete described below:

`t = floor((m * floor(n/c) - floor(n/c) + floor(n/c) - 1) / (m - 1)) = floor(floor(n/c) + (floor(n/c) - 1) / (m - 1)) = floor(n/c) + (floor(n/c) - 1) / (m - 1)`

Sort 1047 Discussions, By:

Please Login in order to post a comment