coins :using recursion

general
1

this is my program but i am unable to fix the bug.
Can anybody help me figure this out.

#include<stdio.h>
int fun(int x);
int main()
{
int test,n,y;
scanf("%d",&test);
while(test--)
{
scanf("%d",&n);
y=fun(n);
printf("%d\n",y);
}
return 0;
}
int fun(int x)
{
int a,b,c,d;
a=x/4;
b=x/3;
c=x/2;
d=a+b+c;
if(x>=d)
return x;
else
{
a=fun(a);
b=fun(b);
c=fun(c);
}
return (a+b+c);
}
2

The test cases are not taken as the input. So take the input as follows :

while((scanf("%lld",&n))!=EOF)
{
     //do something
}

This would start giving you correct answers. But your solution won’t get accepted as for large values it would give time limit exceeded. Hence you will have to precompute values to get it accepted.

1 Like
3

Your function fun(n) is wrong. Following changes will fix it:

  1. You have to check again recursively the maximum value of (x/4), (x/3) and (x/2) before returning it just after the first time i.e., else part should come before if condition and then you have to return the maximum of (a+b+c, x).
  2. Also after you fix the bug the given solution will give TLE verdict as there are large number of cases and you are recomputing the same values again and again. In these type of cases you can memoize your answer so that you don’t have to recompute it in the future. The top down dp would be the best suitable for it. You can implement it using map in C++[STL].
  3. And in the end you have to take the input as suggested by @vermashubhang since the number of test cases is not specified in the question.

If you have any problem in implementing the solution you can refer to the following solution:
Coins Solution

4

hello all… I am continuously getting WA in this ques…link to my soln is http://www.codechef.com/status/COINS,angie…
So plz can anyone fix the bug in the code??