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

  • ansonete + 9 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!

    • abhiranjan + 0 comments

      @ ansonete, it's recommended to write formula instead of code snippet. Will be easier for non-python programmar :)

    • ansonete + 0 comments

      Ok, I updated it, with the input example 10 2 2 and i tried to remove the python stuff and leave only the math symbols :) If anyone has a suggestion how to better rewrite the question is welcome :)

    • zekedroid + 4 comments

      Well, not sure about this formula but if you wanted to use one yourself, think about the steps you would take if you were doing the exchange of wrappers by hand; by the way, not the best code to write as it's confusing and you are writing over the money variable instead of creating a new one. First you buy as many chocolates as you want, chocolates = money/cost . Now you eat those chocolates and exchange all the wrappers possible for extra ones, let's call it extras = chocolates / extra .

      BUT you could have leftover chocolates so let's see how many, remainders = chocolates % extra . Since we got extras , we can add it to the remainders and see if it is enough for more chocolates, super_extras = (extras + remainders) / extra . Remember that all of this is integer division so it'll round down.

      Finish by adding to the total chocolates += extras + super_extras and you're done! You have to tweak it a bit to get edge cases but that part should be trivial. Use the same logic to see where those terms you wrote came from. I think if you rearrange what I showed you'll get the same thing.

      • ganuraag31 + 1 comment

        For just one test case input() There needs changing in condition. What if super_extras is more than m. Then more candies.

        • ssaurabh44 + 0 comments

          Chk this :Worked for all test cases: for(int a1=0;a1 

                  no = n/c;

        int wrapper = no;
        int rem = 0;
        while(wrapper>=m){
            rem = wrapper/m;
            no = no +rem;
            rem = rem + wrapper%m;
            wrapper = rem;


        }

        System.out.println(no);
    }
      • ansonete + 0 comments

        Thanks for your comment. You are right, the code is confusing due the name of the variables :) I updated it.

      • lawless_war1ock + 0 comments

        I am not able to figure out the mistake in this code any help wud be appreciated

        include

        include

        include

        include

        int main() { long int a,b,c,t,d,e; scanf("%ld",&t); while(t--) { scanf("%ld %ld %ld",&a,&b,&c); e=a/b; d=e;

        long int count=0;


while(e>=c)
{
    e=e-c;
    count++;
    e=e+count;

}

printf("%ld",(count+d));


printf("\n");
}

        return 0; }

      • ka1gu0 + 1 comment

        Yeah! You are right and the description is easy. I sloved this problem with the same way. The following is my AC code :)

        int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int t,n,c,m;
    cin>>t;
    while(t--){
        cin>>n>>c>>m;
        int answer=0;
        // Computer answer(the total of chocolates Bob eats)
        // answer consists of two parts: directly buy with money and exchange with wrapper

        int answer1 = n / c; // the number of buying with money
        answer += answer1;

        int answer2 = 0; // the number of exchanging with wrapper

        int wrapper = answer1 / m; // the number of first exchange with wrapper
        int remain = answer1 % m; // the number of first remain wrapper
        answer2 += wrapper;

        int available = wrapper + remain;
        while (available / m != 0) {
            wrapper = available / m;
            remain = available % m;

            answer2 += wrapper;
            available = wrapper + remain;
        }

        answer += answer2;

        cout<<answer<<endl;
    }
    return 0;
}
        • gabrielptp + 0 comments

          Similar approach using python:

          t = int(raw_input().strip())
for a0 in xrange(t):
    n,c,m = raw_input().strip().split(' ')
    n,c,m = [int(n),int(c),int(m)]

result = 0

ch = n / c
result +=ch

while True:

    ch_w = ch / m
    result += ch_w

    ch_r = ch % m   
    ch = ch_w + ch_r

    if ch < m:
        break

print result

    • fizzixio + 0 comments

      I too, would also like to know about this.

    • iiiiii + 0 comments

      thanks for the solution, it reminds me of the meme "code works: no idea why"

    • singhaniya + 0 comments

      sir if you the logic behind it then pls help me to understand that thank you

    • anna_earwen + 5 comments

      @ansonete: This is indeed the cleanest solution, and the logic is simple: for every m wrappers you get a candy, candy = wrapper, i.e. for every m wrappers you get 1 wrapper back. Thus, the actual "wrapper price" of one candy is (m - 1) rather than m. Now, dividing your original number of wrappers by the "reduced price" is unfair - you still have to pay "full price" (i.e. full m) for the very first "exchange candy". Thus, let us first put m aside to make sure we get our first free candy. So the amount of wrappers to divide by reduced price is (boughtCandy - m). Now, the total number of candies is:

      boughtCandy = money / cost

      total = boughtCandy + 1 + (boughtCandy - m) / (m - 1)

      where 1 is the candy we bought for the m we put aside in the first place. This can be simplified as follows:

      total = boughtCandy + (m - 1)/(m - 1) + (boughtCandy - m) / (m - 1)

      = boughtCandy + (m - 1 + boughtCandy - m) / ( m - 1 )

      = boughtCandy + (boughtCandy - 1)/(m - 1)

      Et voila!

      • anderustarroz + 0 comments

        That was brilliant Anna, thanks ;)

      • bhushanz + 0 comments

        thats wrong bud... check for 2nd case of 1st test case

      • ansonete + 0 comments

        Awesome explanation. Thanks a lot.

      • Tejasduseja + 1 comment

        My idea was same as you but i am getting runtime error for test case 5.could u help me?

        • ROBOPRO + 1 comment

          int t,n,m,c; int wrappers,count;

          scanf("%d",t);

          for(int i =0;i 

          wrappers = n/c;
count = wrappers;

while (wrappers >= m)   
{
    wrappers = wrappers - m;
    count = count + 1;
    wrappers = wrappers + 1;
}
printf("%d",count);

          }

          /*The main logic is above u can compare it easily */

      • akshay_sharma96 + 0 comments

        Amazing :)

    • rahultoraskarr + 1 comment

      Here you can find formula with the proof http://www.geeksforgeeks.org/g-fact-42/

      • kujicoso + 0 comments

        I'm trying to understand how this problem can be mapped to a n-ary tree.

        I've tried several approaches but couldn't succeed.

        Could you explain the approach you have in mind?

        Thanks!

    • rohitpal210 + 0 comments

      Here's one way

      int chocolateFeast(int n, int c, int m) {
    int bars,w;
    bars=n/c;
    if(bars<m)
    {
        return bars;
    }
    else if(bars>m)
    {
        w=bars;
        while(w>=m)
        {
            bars+=w/m;
            w=w%m+w/m;
        }

    }
    else
    bars+=1;
return bars;

}