- 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
overt
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 betweenfloor(n/c)-1
(non-inclusive) andfloor(n/c)
(inclusive) multiples ofm
.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 chocolatest = 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