TopCoder problem "BestDecomposition" used in TCHS SRM 3 (Division I Level Three)



Problem Statement

    

A decomposition of a non-negative integer n is a list of non-negative integers that sum to exactly n. The product of a decomposition is the product of all its members. For example, if n = 4, the following decompositions are possible:

4 = 1+1+1+1, product is 1*1*1*1 = 1.

4 = 1+1+2, product is 1*1*2 = 2.

4 = 1+3, product is 1*3 = 3.

4 = 2+2, product is 2*2 = 4.

4 = 4, product is 4.

Given an int n, determine the decomposition of n with the maximal product, and return that product modulo 10007. In the example above, the maximal product is 4 (the product of the decomposition 2 + 2).

 

Definition

    
Class:BestDecomposition
Method:maxProduct
Parameters:int
Returns:int
Method signature:int maxProduct(int n)
(be sure your method is public)
    
 

Constraints

-n will be between 0 and 10000, inclusive.
 

Examples

0)
    
0
Returns: 0
1)
    
1
Returns: 1
2)
    
5
Returns: 6
5 = 2 + 3, 2 * 3 = 6
3)
    
7
Returns: 12
7 = 3 + 4, 3 * 4 = 12
4)
    
9931
Returns: 4664

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5987

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10021&pm=5987

Writer:

gevak

Testers:

PabloGilberto , brett1479 , radeye , Olexiy

Problem categories:

Greedy, Math