# Bytelandian gold coins

qstn look much simpler with recurrence relation

recurrence relation

``````lli oprtn(lli n)

{

if(n<2)

return 0;

lli ans=max(n, oprtn(n/2)  + oprtn(n/3) +oprtn(n/4));// recurrence relation

if(ans>n)

return ans;

else

return n;
}

it can be converted into DP easily by saving the following function

void work()
{
lli i;
learn[0]=0;

learn[1]=1;

learn[2]=2;

learn[3]=3;

for(i=4;i<=1000000000;i++)
{

learn[4]=max(i,learn[i/2]+learn[i/3]+learn[i/4]);

}

}
``````

however size of array is too large(10^9) to accommodate all solution now how to tackle this problem please help

An array of 10^5 to 10^6 will suffice…u dont need to store the higher values…they will not repeat as much…lower values will be encountered larger number of times…if u are unable to understand what i m trying to convey…then u can have a look at a few AC solns…

use the recursive solution with a map<int,int> instead of an array

I wrote this -

#include<stdio.h>

long divide (long x)
{
if ((x/2+x/3+x/4) >= x) return (divide (x/2) +divide (x/3) +divide (x/4)) ;
else return x;

}

int main()
{
long a;
while(scanf("%d",&a)!=EOF)
{
printf("%d\n",divide(a));
}
}

Even though it runs perfectly in my laptop it shows SIGSEGV in codechef

Use map if u know how to use them that will save u the memory problem