Re: [algogeeks] Re: Anyone know optimized solution to bytelandian gold coins problem

2010-09-23 Thread nishaanth 
It is a straight forward dp problem.Use a memoized version. it is pretty
simple.


#includeiostream
#includemap
using namespace std;
map long long int,long long int p;
main()
{
  long long  int a,f;
  long long int fun(long long int );
  p.clear();
  while(cina)
{
  f=fun(a);
  coutfendl;
}
}
long long int fun(long long int a)
{
  long long int ch,q;
  if(a==0)
return 0;
  if(p.find(a)!=p.end())
return p[a];
  else
{
  ch=fun(a/2)+fun(a/3)+fun(a/4);
  if(ch=a)
p[a]=ch;
  else
p[a]=a;
}
  return p[a];
}



-- 
S.Nishaanth,
Computer Science and engineering,
IIT Madras.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Anyone know optimized solution to bytelandian gold coins problem

2010-09-23 Thread Bharath 
Recursion and Memoization.

On Thu, Sep 23, 2010 at 2:12 AM, Dave dave_and_da...@juno.com wrote:

 @Venkatakrishna: What is the problem? I don's see a question.

 Dave

 On Sep 22, 2:36 pm, venkatakrishna bandla
 venkatakrishnabt...@gmail.com wrote:
  You are given a coin, which has an integer number written on it. A
  coin valued n can be exchanged with me for three coins valued n/2, n/3
  and n/4.
  But these numbers are all rounded down to the integer value. You can
  sell these coins for American dollars. The exchange rate is 1:1.

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Bharath

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.