We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Algorithms
  3. Implementation
  4. Chocolate Feast
  5. Discussions

Chocolate Feast

  • icedtrees + 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)
    • Komplex + 0 comments

      @ansonete's solution isn't actually fully correct unless you do the floor of that entire equation, as (floor(n/c) - 1) / (m - 1) represents a possible non-integer value.

      I came to the same formula you did using the same principle.

    • jjlearman + 0 comments

      The first line is wrong:

      t = money + wrappers

      It should be

      t = chocolates + wrappers