Bytelandian gold coins

qstn:COINS Problem - CodeChef

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…:slight_smile:

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