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...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  • Hiring developers?
  1. Practice
  2. Algorithms
  3. Implementation
  4. Chocolate Feast
  5. Discussions

Chocolate Feast

  • Problem
  • Submissions
  • Leaderboard
  • Discussions
  • Editorial
  • Topics

    You are viewing a single comment's thread. Return to all comments →

  • icedtrees 5 years ago+ 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)
    
    10|
    Permalink
    • Komplex 5 years ago+ 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.

      0|
      ParentPermalink
    • jjlearman 4 years ago+ 0 comments

      The first line is wrong:

      t = money + wrappers
      

      It should be

      t = chocolates + wrappers
      
      0|
      ParentPermalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature