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.
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).
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 :)
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.
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);
}
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;
}
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
@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 )
Chocolate Feast
You are viewing a single comment's thread. Return to all 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
Does anyone know the math basis or where this comes from, or where can I read about this?
Thanks!
@ ansonete, it's recommended to write formula instead of code snippet. Will be easier for non-python programmar :)
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 :)
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
moneyvariable 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 itextras = chocolates / extra.BUT you could have leftover
chocolatesso let's see how many,remainders = chocolates % extra. Since we gotextras, we can add it to theremaindersand 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_extrasand 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.For just one test case input() There needs changing in condition. What if super_extras is more than m. Then more candies.
Chk this :Worked for all test cases: for(int a1=0;a1
Thanks for your comment. You are right, the code is confusing due the name of the variables :) I updated it.
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;
return 0; }
Yeah! You are right and the description is easy. I sloved this problem with the same way. The following is my AC code :)
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 resultI too, would also like to know about this.
thanks for the solution, it reminds me of the meme "code works: no idea why"
sir if you the logic behind it then pls help me to understand that thank you
@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 / costtotal = 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!
That was brilliant Anna, thanks ;)
thats wrong bud... check for 2nd case of 1st test case
Awesome explanation. Thanks a lot.
My idea was same as you but i am getting runtime error for test case 5.could u help me?
int t,n,m,c; int wrappers,count;
for(int i =0;i
}
/*The main logic is above u can compare it easily */
Amazing :)
Here you can find formula with the proof http://www.geeksforgeeks.org/g-fact-42/
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!