Computer Science Canada

Decomposition of a number.
Author:  MysticVegeta [ Tue Jun 27, 2006 1:08 pm ]
Post subject:  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.
Author:  wtd [ Tue Jun 27, 2006 1:14 pm ]
Post subject: 
Recursion is the "math way." Smile
Author:  Andy [ Tue Jun 27, 2006 2:53 pm ]
Post subject: 
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.

code:
#include <iostream>
#include <cmath>
using std::cout;
using std::endl;

int main()
{
    int x = 20;
   
        if ((x % 3) == 0)
                cout << (int)(pow (3, x / 3)) % 10007 << endl;
        else if ((x % 3) == 1)
                cout << (int)(pow (3, ((x - 4) / 3)) * 4) % 10007 << endl;
        else
                cout << (int)(pow(3, x / 3) * 2) % 10007 << endl;
   
    return 0;
}


or

code:

#include <iostream>
#include <cmath>

int main()
{
        int x = 10;

        std::cout << (int)(pow (3, (x - ((x % 3) % 2))/ 3) * ((x % 3) ? pow(2, 3 - (x % 3)): 1)) % 10007 << std::endl;

        return 0;
}


this should get you the largest product everytime
Author:  Martin [ Tue Jun 27, 2006 8:03 pm ]
Post subject: 
Andy wrote:
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 % 3 = 2, use (x-2) % 3, and one 2.


Hey,

Can you go into a bit more depth here?
Author:  zylum [ Tue Jun 27, 2006 8:03 pm ]
Post subject: 
andy, do you do topcoder? if not, you should Wink
Author:  Andy [ Tue Jun 27, 2006 9:26 pm ]
Post subject: 
zylum, i've been wanting to get into it for a while.. i guess i can give it a try over my next work term (starting at the end of august), hopefully that'll increase my chance of getting a co op job at google haha..

martin,
(x-2)*2 >= x for all x>=4 shows that if you have any number greater than 4, breaking it up to 2s will increase the product,

3+3=6=2+2+2 and 3^2>2^3, this shows, that if you have a 6, its better to break it up into 3s rather than 2s. so we want to break the number down to 3s.

but lets you say you have n mod 3 = 1, this means, you'll get (n-1)/3 3s, and a 1, but that 1 doesnt increase your product. since 3+1 = 4 = 2+2, and 2*2 > 3*1, when ever we have such a case, its better to break off two 2s, and the rest into 3s.
Author:  MysticVegeta [ Wed Jun 28, 2006 11:40 am ]
Post subject: 
Andy wrote:
3+3=6=2+2+2 and 3^2>2^3, this shows, that if you have a 6, its better to break it up into 3s rather than 2s. so we want to break the number down to 3s.


wait a sec, dont you mean, breaking it up into 3s would make 2 * 2 * 2 = 8. but breaking it up into 2s would make 3 * 3 = 9. which is greater. Is that a typo or am I misunderstanding something?
Author:  zylum [ Wed Jun 28, 2006 12:01 pm ]
Post subject: 
MysticVegeta wrote:
Andy wrote:
3+3=6=2+2+2 and 3^2>2^3, this shows, that if you have a 6, its better to break it up into 3s rather than 2s. so we want to break the number down to 3s.


wait a sec, dont you mean, breaking it up into 3s would make 2 * 2 * 2 = 8. but breaking it up into 2s would make 3 * 3 = 9. which is greater. Is that a typo or am I misunderstanding something?


breaking into 3s means 3+3 = 6. note the 3s.
Author:  MysticVegeta [ Wed Jun 28, 2006 2:10 pm ]
Post subject: 
oh I thought into 3 numbers... 2 + 2 + 2.. sorry for the confusion, Thanks for the answer guys, if I needed to create this using recursion how would I do that? something like this:

code:
//Pseudo
void solve (sum : int, n : int)
if (sum == n) {
     max = Math.max (max, current);
     current = 1;
     return;
}

for (int i = 0; i <= sum; i++) {
       solve (sum, n + i);
       current *= i;
}


I dont really know what I am doing. Thanks again for the math solution.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy