Re: [algogeeks] Re: Anyone know optimized solution to bytelandian gold coins problem
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
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.
[algogeeks] Re: Anyone know optimized solution to bytelandian gold coins problem
@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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.