TopCoder problem "AvoidingProduct" used in SRM 399 (Division I Level One , Division II Level Three)



Problem Statement

    

You are given a set A of integers and a positive integer n. You must find positive integers x, y and z such that their product is as close to n as possible (minimize |n - x * y * z|), and none of them belongs to A. If there are several such triples, find the one with the smallest x. If there are still several such triples, minimize y. If there is still a tie, minimize z.

You are given the elements of A as a int[] a. Return a int[] with exactly three elements: x, y and z, in this order.

 

Definition

    
Class:AvoidingProduct
Method:getTriple
Parameters:int[], int
Returns:int[]
Method signature:int[] getTriple(int[] a, int n)
(be sure your method is public)
    
 

Constraints

-a will contain between 0 and 50 elements, inclusive.
-Each element of a will be between 1 and 1000, inclusive.
-All elements of a will be distinct.
-n will be between 1 and 1000, inclusive.
 

Examples

0)
    
{2,4}
4
Returns: {1, 1, 3 }
You can get 3=1*1*3 and 5=1*1*5. 3 is better.
1)
    
{1}
10
Returns: {2, 2, 2 }
2)
    
{1,2}
10
Returns: {3, 3, 3 }
3)
    
{1,3}
12
Returns: {2, 2, 2 }
4)
    
{1,3}
13
Returns: {2, 2, 4 }
5)
    
{1,15}
90
Returns: {2, 5, 9 }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12171&pm=8758

Writer:

andrewzta

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Math, Search