coin problem(giving result for small no.s but in question if no. is 1000000000 then not able to define array of that or n/4 length)

7 views
Skip to first unread message

vineet gandhi

unread,
Mar 13, 2011, 8:34:11 AM3/13/11
to Coders in NIT Durgapur
import java.util.Scanner;

/**
*
* @author roger
*/
public class Main {
static int arr[]=new int[1000000];
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner s=new Scanner(System.in);

int x = s.nextInt();
for(int i=0;i<x;i++)
{int a=s.nextInt();
int z= func(a);
System.out.println(z);
}

}
static int func(int q)
{if(q<12)
{
return q;
}
if(arr[q]==0)
{
arr[q]=func(q/2)+func(q/3)+func(q/4);

}
return arr[q];
}

}

Navin Agarwal

unread,
Mar 13, 2011, 9:15:31 AM3/13/11
to nitdc...@googlegroups.com
You need to use some data structure like map in c++, for storing the values.


--
Navin Agarwal

anoop chaurasiya

unread,
Mar 13, 2011, 9:45:35 AM3/13/11
to nitdc...@googlegroups.com
@vineet, as the constraints don't allow u to use the complete memoisation, u may use memoisation up to some extent and recalculate if the numbers are too big...here is the idea...

#define MAX 10000000
int best[MAX]={-1};
int calc(int n)
{
if(n<MAX)
{
if(already calculated)
return best[n];
else
best[n]=/* calculate best */;
}
return /*calc best*/;
}
--
Anoop Chaurasiya
CSE (2008-2012)
NIT DGP

vineet gandhi

unread,
Mar 13, 2011, 2:08:59 PM3/13/11
to Coders in NIT Durgapur
thanks a lot!!!


On Mar 13, 6:45 am, anoop chaurasiya <anoopchaurasi...@gmail.com>
wrote:
> NIT DGP- Hide quoted text -
>
> - Show quoted text -

Manish Agrahari

unread,
Mar 14, 2011, 12:05:46 AM3/14/11
to nitdc...@googlegroups.com
As mailed by Navin, Today (Monday) there is class of Algo. The topic for today is

1)Bitset and its application
2)Some interesting problems.


        Time    :    6:00 pm
        Date     :    14th March
        Venue   :    D.M.Sen Complex

This'll be taken by Anoop, Navin.

@vineet ,abhishek ,shalini please inform to your branch-mates for this class through respective groups..

Thanks
--
Manish Kumar Agrahari
CSE :: 3rd year
National Institute of Technology,
Durgapur
Reply all
Reply to author
Forward
0 new messages