Can be solved by dynamic programming. It can scale also even when we expand this and introduce the 5, 6, or more coefficients.
Think of small stuff first. We know immediately the solution of x1 = n has only 1 solution. We also know that the solution of 2x2 + x1 = n will have floor(n/2) + 1 solution (basically, trying x2 = [0,1,...floor(n/2)] ... and whatever left of this can be solved in 1 way (see the x1 = n solution above). It's easy to have the solution for 2x2 + x1 = n available and let's assume that we have this in ways[0..n-1] array. For number of solution for 3x3 + 2x2 + x1 = n, start with trying x3 = 0, 1, ... floor(n/3). For x3 = 0, we have ways[n] solution, for x3 = 1, we have ways[n-3] solution ... etc. Same rule applies to 4x4. For this, I'd prefer top down with memoization method rather than bottom up as explained above. On 2/11/07, Jair Cazarin <[EMAIL PROTECTED]> wrote: > > I think that a simple backtracking approach could solve this problem. > > On 2/11/07, [EMAIL PROTECTED] < [EMAIL PROTECTED]> wrote: > > > > > > I`m trying to solve http://acm.mipt.ru/judge/problems.pl?problem=201. > > I`ve tried googling but couldn`t get any way to approach the problem. > > Brute force is ruled out, so how can we solve this problem? > > > > > > http://slipvayne.googlepages.com > > > > > > -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
