TopCoder problem "TriangleConstruction" used in TCHS07 Gamma 1 (Division I Level One)



Problem Statement

    

The perimeter of a triangle with edge lengths a, b and c is a + b + c.

You have several sticks of various lengths. The int[] lengths contains the length of each stick. Return the maximum possible perimeter of a triangle that can be constructed with your sticks. Each edge of the triangle must be constructed using exactly one stick. You are not allowed to break sticks into smaller pieces. Return -1 if no triangle can be constructed.

 

Definition

    
Class:TriangleConstruction
Method:greatestPerimeter
Parameters:int[]
Returns:int
Method signature:int greatestPerimeter(int[] lengths)
(be sure your method is public)
    
 

Notes

-You can construct a triangle with edge lengths x <= y <= z if and only if x + y > z.
 

Constraints

-lengths will contain between 3 and 50 elements, inclusive.
-Each element of lengths will be between 1 and 1000, inclusive.
 

Examples

0)
    
{1,2,2}
Returns: 5
In this case there is only one possible triangle, and its perimeter is 1+2+2=5.
1)
    
{2,3,2,3,2,4}
Returns: 10
2)
    
{1,2,3}
Returns: -1
No triangle can be constructed from these sticks.
3)
    
{4, 5, 6, 7, 20}
Returns: 18
4)
    
{214, 108, 273, 467, 991, 434, 767, 659}
Returns: 2417
5)
    
{116, 373, 471, 540, 350, 318, 804, 561, 428, 915, 64, 853, 498, 600, 439, 732, 139, 497, 512, 510, 796}
Returns: 2572

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10703&pm=7523

Writer:

andrewzta

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Simple Math, Simple Search, Iteration