-----------------------------------

MysticVegeta

Tue Jun 27, 2006 1:08 pm


Decomposition of a number.

-----------------------------------

For eg:

1 + 1 + 1 + 1 = 4. 
1 + 1 + 2 = 4
2 + 2 = 4
1 + 3 = 4
4 = 4.

Now I have to output the max product as a result of any decomposition:

like: 

1 * 1 * 1 * 1 = 4
1 * 1 * 2 = 2
2 * 2 = 4
1 * 3 = 3
4 = 4

max product is 4 and I have to output the product % 10007

so 4 % 10007 = 4.

Most people did this using a while loop and some math. Unfortunately I lack that knowledge. Could someone please help me with both recursion and math way? Thanks a lot.


-----------------------------------

wtd

Tue Jun 27, 2006 1:14 pm



-----------------------------------

Recursion is the "math way."  :)


-----------------------------------

Andy

Tue Jun 27, 2006 2:53 pm



-----------------------------------

no, its the dumb way =P

Notice that (x-2)*2 >= x for all x>=4, and that 3^2>2^3


this shows that inorder to obtain the largest product, you want as many 3s as possible without getting any 1s. 
so if x mod 3 = 0, divide it up to all x/3 3s, if x mod 3 = 1, use (x - 4) / 3 and two 2s, and if x mod 3 = 2, use (x-2) / 3 3s, and one 2. 

#include 
#include 
using std::cout;
using std::endl;

int main()
{
    int x = 20;
    
	if ((x % 3) == 0)
		cout