I was trying The Bytelandian Gold coin problem mentioned here - http://www.codechef.com/problems/COINS/ here is one of its solution-
#include <stdio.h>
long int a[30][19]; //1
long int recur(long int n, int i, int j);
int main()
{
long int n;
int i, j;
while (scanf("%lld", &n) != EOF)
{
for (i = 0; i < 30;i++)
for (j = 0; j < 19; j++)
a[i][j] = 0;
long int v = recur(n, 0, 0);
printf("%lld\n", v);
}
return 0;
}
long int recur(long int n, int i, int j)
{
if (n <12 ) //2
return n;
else if (!a[i][j])
{
long int t = recur(n / 2, i + 1, j) + recur(n / 3, i, j + 1) + recur(n / 4, i + 2, j);
a[i][j] = t;
}
return a[i][j];
}
In this code I cannot understand two points- 1-the size of array a[30][19] which is based on the maximum number of times the maximum value of the input number is divisible by 2 or 3 for which they use some log base 2 or 3 formula to find.Can someone please explain this formula,is this some mathematical property if yes where can I find more information about it. 2-to stop the recursion n<12 condition was used as all numbers below 12 will have values equal to itself as max value.I cannot understand how it was found.I mean how they find 12 is the limiting value also if I replaced the original recur function with this I get wrong answer-
long int recur(long int n, int i, int j)
{
if ((n == 0) || (n == 1) || (n == 2) )
return n;
else if (!a[i][j])
{
long int t = recur(n / 2, i + 1, j) + recur(n / 3, i, j + 1) + recur(n / 4, i + 2, j);
a[i][j] = n> t ? n : t;
}
return a[i][j];
}
I would be grateful if someone please explains the above 2 points