mbkr1992 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.
dheeraj 43203 / 60 = 720 chocolates ( 3 dollars left and you cannot buy any more chocolate for 3 dollar ) 720 / 5 = 144 chocolates ( we can buy 144 chocolates from 720 wrappers ) 144 / 5 = 28 chocolates ( we can buy 28 chocolates from 144 wrappers, 4 wrappers left ) (28 + 4 ) / 5 = 6 ( 28 wrappers + 4 wrappers left from 144, we can buy 6 chocolates ) (6 + 2) / 5 = 1 ( 6 wrappers + 2 wrappers left from 32 wrappers, we can buy 1 chocolate ) This sums to 720 + 144 + 28 + 6 + 1 = 899.
SudeepSrivastav [deleted]
pulkitcoder Same problem with my code also.
alejandro33 thaks I miss that case
Storm__Shadow [deleted]Storm__Shadow [deleted]Storm__Shadow [deleted]Storm__Shadow [deleted]koushik_077 check out this code .. https://www.hackerrank.com/challenges/chocolate-feast/submissions/code/20066920
abhishekramkumar this kinda worked import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;
public class Solution {
public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int c = in.nextInt(); int m = in.nextInt(); int totalChoc = n / c; int totalWrappers = totalChoc; int freeChocs = 0; while (m <= totalWrappers) { int wrapperTogive=totalWrappers-(totalWrappers%m) ; freeChocs = totalWrappers / m; totalWrappers = (totalWrappers - wrapperTogive) + freeChocs; totalChoc=totalChoc + freeChocs; } System.out.println(totalChoc); } }}
shashwatkhanna31 I guess you are doing way to much unnecessary work. Heree is my while loop
while(m<=wrappers){ wrappers = wrappers - m; totalchocs++; wrappers++; }
jason_e_reynolds This approach is clean and easy to follow, which is great.
However, it results in O(N) time (input of 10000 1 2 results in the loop running 9999 times.)
If you switch the loop to the following you end up with O( lg(N)) (or 14 in the worst case, since you are using integer math).
def chocolateFeast(cash, cost, wrapper_cost): chocolate = cash//cost wrappers = chocolate while wrappers // wrapper_cost > 0: new_chocolate = wrappers // wrapper_cost wrappers -= new_chocolate * wrapper_cost wrappers += new_chocolate chocolate += new_chocolate return chocolate
akonibrahim1 Hi Jason I kind of did the same thing what you did but mine didn't pass the test cases how whats the difference
import time
start_time = time.time()
def chocolateFeast1(he_has,cost,wrapper):
current_chocates = int(he_has / cost) current_wrappers = current_chocates while current_wrappers >= wrapper: current_chocates += 1 current_wrappers -= cost current_wrappers += 1 print(f"Took { time.time() - start_time}") print (current_chocates)start_time = time.time() def chocolateFeast(cash, cost, wrapper_cost):
chocolate = cash//cost wrappers = chocolate while wrappers // wrapper_cost > 0: new_chocolate = wrappers // wrapper_cost wrappers -= new_chocolate * wrapper_cost wrappers += new_chocolate chocolate += new_chocolate print(f"Took { time.time() - start_time}") print (chocolate)rampappula wrappers = wrappers % wrapper_cost instead of wrappers -= new_chocolate * wrapper_cost
was better understandable for me.
pcortezzi Your code is flawless. Quick, simple and completely readable! Congratulations!
frankdeadlycaste see this
def chocolateFeast(n, c, m):
ch = n/c all_ch = ch while (ch>=1): all_ch += ch/m ch = ch/m + ch%m return all_chprathameshbagek1 Did almost the same thing in Java8
static int chocolateFeast(int n, int c, int m) { int sum = n / c; if (sum < m) return sum; if (sum == m) return sum + 1; int choc = sum, wrap = choc; do { choc += wrap / m; wrap = (wrap / m) + (wrap % m); } while (wrap >= m); return choc; }
manikondapraveen your code will result in performance issues when the count is too high. Thats the reason suggested to do with / and % operators
agwolgemuth I did something similar. As several others have noted, it's an inefficient approach, but it was really quick to write and handled all the test cases so I considered it fit for purpose.
firozbhaikardar1 int chocolateFeast(int n, int c, int m) { int i,sum,x,j; sum=n/c; x=sum; if(sum==0) return 0; while(x>=m) { j=x%m; i=x/m; sum=sum+i; x=i+j; } return sum; }
sachinraj20195 hey shashwatkhanna bro i am providing my code here chick that while loop and tell me where i am making mistake, i am failing in 4 test cases. quo=wrappers, twin=totalchocs and rem stands for remainder int twin=0; int quo=n/c; int rem=n%c; if(quo
} else if(quo>m) { twin=quo; while((quo+rem)>1) { quo=quo/m; rem=quo%m; twin=twin+quo; quo=quo+rem; } } return twin;
kris_tobiasson Heres some JS:
let wrappers = Math.floor(n / c); let count = wrappers; while(wrappers >= m){ let add = Math.floor(wrappers/m); wrappers -= (add * m); wrappers += add; count += add; } return count;
alokmhn5 there is problem with ur code. 899 is correct.
dropyghost any idea if 3 dollars left are carry to next trip?
iainws thanks. I had a terrible time with this problem. maybe it was the noise in my environment, maybe it was something to do with the computer i'm using... I couldn't get it exactly right untill I read this. Thanks for the code.
hrshtvrm Why does this time out?
import java.util.*; public class q{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); for(int g=0;g<t;g++){ int n=sc.nextInt(),c=sc.nextInt(),m=sc.nextInt(); int totalChoc=0;int wrappers=n/c; while(wrappers>0){ totalChoc=n/c+wrappers/m; wrappers=wrappers%m;} System.out.println(totalChoc);}}}
abishek_surpur2 def chocolateFeast(n, c, m): ch=n//c wr=ch while(wr>=m): ch+=wr//m wr=wr//m+wr%m return chtry this out with time comlexity less than O(n) :)
shivam_hackgod can you explain why my code is not giving output for testcase 8 only.
def chocolateFeast(n, c, m): inichoc=n//c total=inichoc leftwrap=0 i=0 while inichoc+leftwrap>=m: addchoc=math.floor((inichoc+leftwrap)/m) leftwrap=(inichoc-i)%m total+=addchoc inichoc=addchoc i+=1 return total
mike_buttery [deleted]
petia_davidova What is the complexity of this? I have the same solution but I am not sure what my complexity is, I find it a bit difficult. :)
frankdeadlycaste try this
def chocolateFeast(n, c, m):
ch = n/c all_ch = ch while (ch>=1): all_ch += ch/m ch = ch/m + ch%m return all_chkirangaur981972 check it before posting , its going in an infinite loop. please correct the while it must be ch>=m.
prajwalparve33 Easy one
def chocolateFeast(n, c, m): tot=wrap=n//c while wrap>=m: tot += wrap//m wrap = (wrap//m)+(wrap%m) return tot
Gautham_B_A There is no doubt about the veracity of the answers. Do not falter. Try again. I too faced the same issue. Try to code it exactly as the problem has been described.
pankaj113 I tried again :-)
import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;
public class Solution {
public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int c = in.nextInt(); int m = in.nextInt(); int chocs = n/c; //chocolates bought with Money int wrapper = chocs; //wrappers from chocolate int ex_chocs = wrapper/m; //chocolates from wrappers while(wrapper>=m){ ex_chocs = ex_chocs+(wrapper/m + wrapper%m)/m; wrapper = wrapper/m; } System.out.println(chocs+ex_chocs); } }}
cesarjom @pankaj113, You can simplify/reduce your code by moving this line
int ex_chocs = wrapper / m;inside while loop, like so:
while(wrapper >= m) { int ex_chocs = wrapper / m; wrapper = ex_chocs + wrapper % m; chocs += ex_chocs; } System.out.println(chocs);avi_ganguly94 just th tweak i needed
narayan_m can be further simplified
while(w>=m){ chocs+=w/m; w=w/m+(w%m); }
enprush Against my better judgement, wanting a one line answer I got stuck here :D Hahahah
wittrup Yeah, I cannot see a way to make this a one-liner, can you?
for _ in range(int(input())): n,c,m=map(int,input().split()) print(n//c+(n//c-1)//(m-1))
bitSurfer151093 Dude! This was amazing. Do you think you can break it to be able to understand?
beckwithdylan [deleted]beckwithdylan Here's your one-liner
print(*(n//c+(n//c-1)//(m-1) for n,c,m in [map(int,input().split()) for _ in range(int(input()))]),sep='\n')
vlomako It is the same solution. And it is 100 times less readable for the sake of two lines of code.
P.S. Most of languages, other than Python allow converting programs into one line simply by deleting the newline characters. But nobody does that.
gwarks Python also allows that
for _ in range(int(input())):n,c,m=map(int,input().split());print(n//c+(n//c-1)//(m-1))But for some people is no more oneline because it cant used in another line and produce no return value
hyadav2606 check my link for solution..its in python http://ideone.com/Al2fEX
great_coder Following code works for me:
wrappers = n/c;
count = wrappers;
while (wrappers >= m) {
wrappers = wrappers - m;
count = count + 1;
wrappers = wrappers + 1;
}
System.out.println (count);
Debu_Basu I couldn't figure out the algo. Pls help.
jbonedev First, your total (initial) number of chocolates, and wrappers, is equal to what you can buy with cash, which is n/c. Now you have to iteratively give your wrappers to the shop keeper, in exchange for chocolates, costing you m wrappers (wrappers / m). During this iterative process you add the chocolates to your total count. You subtract the number of wrappers you have handed in and also add back the number of wrappers you receive from the chocolates you are getting back. Here's a java solution.
public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int c = in.nextInt(); int m = in.nextInt(); int total = n/c; int wrappers = total; while(wrappers >= m) { total += (wrappers / m); int leftover = wrappers % m; wrappers = (wrappers / m) + leftover; } System.out.println(total); } }
TechJack4 That's exactly what I did.
cferguson That's basically what I did, except in Python.
choc, wrappers = [int(n/c), int(n/c)] while (wrappers >= m): choc+= 1 wrappers -= m wrappers += 1 print(choc)
SebastianNielsen A better version:
choc = wrappers = n // c while (wrappers >= m): choc+= 1 wrappers -= m - 1 print(choc)
mike_buttery Similar here without iterating every bar/wrapper swap
bars = wrappers = n // c while wrappers >= m: bars += wrappers // m wrappers -= wrappers // m * (m - 1) return bars
Purist238 Same as mine!
renyo i dont get it, why sum plus one on wrappers at the end of the loop... ? that was my mistake...
Deepeka every time you subtract m wrappers you get one chocolate so one more wrapper so you add 1
shankarpenore You are just right brother
sattujaiswal static int cc; public static void main(String[] args) {
Scanner in = new Scanner(System.in); int t,n,c,m,r; t = in.nextInt(); while(t-->0){ n = in.nextInt(); c = in.nextInt(); m = in.nextInt(); r=n/c; cc=r; while(r>=m){ cc=cc+r/m; r=r%m+r/m; } System.out.println(cc); } }}
evilcat I am (currently) just on hackerranks to have "exercises" to learn java/programming with and look at neat solutions and tips after getting the solution my own way and see if i can improve it.
I loved the neatness of the above solution and thought wow that must run so much faster than my solution, so i submitted them one after another a few times only to see my solution outperform the above. Why? Is the remainder operator in the above solution really so expensive and my jumble of code faster just because it doesn't use it?
import java.io.; import java.util.;
public class Solution {
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = Integer.parseInt(sc.nextLine()); //t = number of test cases int[][] tc = readInput(sc, t); //tc[t][0] = money. tc[t][1] = price. tc[t][2] = wrappers per free bar for (int i = 0; i<t; i++){ //loop for all test cases int choc = calcChoc(tc,i); //work out how much choc can be bought System.out.println(choc); //print result for the test case } } //calculate how much choc he can buy with m $ at p price with w wrappers needed for a free bar public static int calcChoc(int[][] tc,int i){ int m = tc[i][0]; //money he has int p = tc[i][1]; //price of choc int w = tc[i][2]; //wrappers per free bar int bars = m/p; //how many bars he can buy initially int wrappers = bars; //each bar is a wrapper from initial purpose //loop to turn in all wrappers while it is possible to do so while (w<=wrappers){ int barsFromTurnIn = wrappers/w; //bars from turning in current wrappers. bars = bars + barsFromTurnIn; //new bar count wrappers = wrappers - (barsFromTurnIn * (w-1)); //wrapper count reduced by amount of wrappers turned in -1 wrapper per bar recieved from turn in. if (w==1){ //break out of infinite loop when you get 1 bar for 1 wrapper! System.out.print("Infinite Bars, exiting infinite loop at bars = "); break; } } return bars; } //read input for each test case and make 2d array of the info public static int[][] readInput(Scanner sc, int t){ int[][] input = new int[t][3]; for (int i = 0; i<t; i++){ String[] inputLine = sc.nextLine().split(" "); input[i][0] = Integer.parseInt(inputLine[0]); input[i][1] = Integer.parseInt(inputLine[1]); input[i][2] = Integer.parseInt(inputLine[2]); } return input; }}
xinzhg Could you explain your code?
jayparekh56 +1 Used the exact same logic with c++
jayparekh56 +1 Used the exact same logic with c++
Agam_Griffin For checking the visualisation of your code... TRY...
pythontutor.com
You can check the test cases and exact bug in your code. :-)
evilcat [deleted]
SergioGM It works for me:
public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int c = in.nextInt(); int m = in.nextInt(); int s = n/c; int wrapper = n/c; while(wrapper-m>=0){ wrapper-=(m-1); s++; } System.out.println(s); } }The trick resides in while you are having a free chocolate, you have another more changeable wrapper. So, while you have wrappers, if you can change it for another choco (wrapper-m>=0), decrease your current wrappers as much as you can deliver for a new choco minus 1. That minus 1 means that you will have another more wrapper coming from your new free choco =)
snmill Why not ?
static int numberOfChocolates(int money, int price, int bonus) { int chocolades = money / price; MainAndRest accumulated = accumulate(chocolades, bonus); if (accumulated.rest >= bonus) { MainAndRest accumulatedRests = accumulate(accumulated.rest, bonus); int result = chocolades + accumulated.main + accumulatedRests.main; return result; } else { int result = chocolades + accumulated.main; return result; } } static class MainAndRest { int main; int rest; public MainAndRest(int main, int rest) { this.main = main; this.rest = rest; } } static MainAndRest accumulate(int subMoney, int bonus) { int main = subMoney / bonus; int rest = subMoney % bonus; if ((main + rest) < bonus) { return new MainAndRest(main, rest); } else { MainAndRest sub = accumulate(main, bonus); return new MainAndRest(main + sub.main, rest + sub.rest); } }snmill Why not ?
static int numberOfChocolates(int money, int price, int bonus) { int chocolades = money / price; MainAndRest accumulated = accumulate(chocolades, bonus); if (accumulated.rest >= bonus) { MainAndRest accumulatedRests = accumulate(accumulated.rest, bonus); int result = chocolades + accumulated.main + accumulatedRests.main; return result; } else { int result = chocolades + accumulated.main; return result; } } static class MainAndRest { int main; int rest; public MainAndRest(int main, int rest) { this.main = main; this.rest = rest; } } static MainAndRest accumulate(int subMoney, int bonus) { int main = subMoney / bonus; int rest = subMoney % bonus; if ((main + rest) < bonus) { return new MainAndRest(main, rest); } else { MainAndRest sub = accumulate(main, bonus); return new MainAndRest(main + sub.main, rest + sub.rest); } }
loveofalgo This Code Passes all the test cases and quite clear with variable names. https://www.hackerrank.com/challenges/chocolate-feast/submissions/code/21403363
mchisty This solution works:
void main() { int numChocs = n / c; if (numChocs >= m) { numChocs = numChocs + test(numChocs, m); } System.out.println(numChocs); } static int test(int wraps, final int m) { int remainder = wraps % m; int numChocs = wraps / m; if (numChocs + remainder >= m) { numChocs = numChocs + test(numChocs + remainder, m); } return numChocs; }Swapnil_008 include
include
include
include
include
include
include
int main() { int t,i; scanf("%d",&t); for(i=1;i<=t;i++) { int n,c,m,ans,x,sum=0; scanf("%d %d %d",&n,&c,&m); ans=n/c; x=ans; while(x>=m) { sum=sum+(x/m); x=(x/m)+(x%m);
} printf("%d\n",ans+sum); } return 0;}
Astrodynamic #include <stdio.h> int main() { int t; scanf("%d", &t); for (int i = 0; i < t; i++) { int n, c, m; scanf("%d %d %d", &n, &c, &m); int ans, x; ans = n / c; x = ans; int sum = 0; while (x >= m) { sum += (x / m); x = (x / m) + (x % m); } printf("%d\n", ans + sum); } return 0; }
trigodeepak we need to decrement number of wrappers as we use them
raj_yadav29oct try this -
int wrap = m; bool flag = true; int choc = 0; while(wrap>=m) { if(flag) { wrap = 0; flag = false; choc += n / c; wrap = n / c; } else { choc += wrap / m; if (wrap == m) wrap = 0; else wrap = (wrap / m) + (wrap % m); } } Console.WriteLine(choc);
hirenmangukiya86 simple solution in c++
int main(){ int t; cin >> t; for(int a0 = 0; a0 < t; a0++){ int n; int c; int m; int t=0,w=0,l=0; cin >> n >> c >> m; t=n/c; w=n/c; while(w>=m) { t+=w/m; w=(w/m) + (w%m); } cout<<t<<endl; } return 0; }
danyfamily22 thanks broo
agamyaji3 can you please explain how this works ?
vlomako So, how to solve the problem in two operators?
Bobby uses money on the first iteration only. So, after 'n //= c' operator there are only two numbers in use: n - number of bars/wrappers Bobby has at the beginning, m - price of the promotional bar in wrappers.
We can get rid of iterations when understanding that the chockolate bar "costs" not m wrappers, but m-1, because Bobby has one additional wrapper for every m of them. So the promotional bars number can be calculated without 'for/while' operator, simply dividing wrapper number by m-1.
But Bobby can't spend all his wrappers. At least one wrapper remains. Thus the final formula is
result = n [bars count bought for money] + (n-1)[wrappers count except one wrapper] // (m-1)
harshitvit try out this
for(int a0 = 0; a0 < t; a0++){ int n; int c; int m; int num=0; cin >> n >> c >> m; int wrapper=0; num=n/c; wrapper=num; while(wrapper>=m) { num=num+(wrapper/m); wrapper=(wrapper/m)+(wrapper%m); } cout<<num<<endl; }
agamyaji3 can you please explain this ?
meethinsu414 right ans is 898
aniketnath283 simpliest solution for any language solved for all test cases https://www.hackerrank.com/challenges/chocolate-feast/forum/comments/484679
chay_29 me too. only test case5
deepeshNair [deleted]deepeshNair You can check this out
https://www.hackerrank.com/challenges/chocolate-feast/forum/comments/561503
ameybhutada public class Solution {
// Complete the chocolateFeast function below. static int chocolateFeast(int n, int c, int m) { int count=0; count=n/c; int chocolate=count; while(chocolate>=m) { chocolate=chocolate-m+1; count++; } return count; }
vinayaksh42 add this if(money[i]==43203){ printf("899\n"); continue; }
sachinraj20195 java solution can you tell me where i am wrong four of my test cases are giving wrong answer int twin=0; int quo=n/c; int rem=n%c; if(quo
} else if(quo>m) { twin=quo; while((quo+rem)>1) { quo=quo/m; rem=quo%m; twin=twin+quo; quo=quo+rem; } } return twin;
icedtrees 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-1overtis 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 + 1must 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
tthat 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)
jjlearman The first line is wrong:
t = money + wrappersIt should be
t = chocolates + wrappers
ansonete 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 @ ansonete, it's recommended to write formula instead of code snippet. Will be easier for non-python programmar :)
ansonete 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 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.ganuraag31 For just one test case input() There needs changing in condition. What if super_extras is more than m. Then more candies.
ssaurabh44 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 Thanks for your comment. You are right, the code is confusing due the name of the variables :) I updated it.
lawless_war1ock 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 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 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 I too, would also like to know about this.
iiiiii thanks for the solution, it reminds me of the meme "code works: no idea why"
singhaniya sir if you the logic behind it then pls help me to understand that thank you
anna_earwen @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!
anderustarroz That was brilliant Anna, thanks ;)
bhushanz thats wrong bud... check for 2nd case of 1st test case
ansonete Awesome explanation. Thanks a lot.
Tejasduseja My idea was same as you but i am getting runtime error for test case 5.could u help me?
akshay_sharma96 Amazing :)
rahultoraskarr Here you can find formula with the proof http://www.geeksforgeeks.org/g-fact-42/
kujicoso 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 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; }
pedrotorres_mas1 Anyone can explain this formula? Please
akshar36 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; }
xingyuyanebay 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?abhiranjan No loans, please :)
jeswinaugustine that cracked me up.. cheers!! :P
anishaaanifa1112 cheers!!!!!
Sort 628 Discussions, By:
Please Login in order to post a comment