Problem:
TopCoder Problem Statement - Workshop |
Single Round Match 166 Round 1 - Division II, Level One |
Overview:
Determine the number of triangles that can be formed given a set of lengths.
Java Source:
01: public class Workshop { 02: 03: public int pictureFrames(int[] pieces) { 04: 05: int count = 0; 06: 07: /* 08: * Loop through all possible combinations of side1, side2, and side3 09: */ 10: for (int side1 = 0; side1 < pieces.length - 2; side1++) { 11: int s1 = pieces[side1]; 12: 13: for (int side2 = side1 + 1; side2 < pieces.length - 1; side2++) { 14: int s2 = pieces[side2]; 15: 16: for (int side3 = side2 + 1; side3 < pieces.length; side3++) { 17: int s3 = pieces[side3]; 18: 19: // Ensure the sum of any 2 sides is greater than the 3rd. 20: if ( 21: ((s1 + s2) > s3) && 22: ((s1 + s3) > s2) && 23: ((s2 + s3) > s1) 24: ) count++; 25: 26: } 27: } 28: } 29: 30: return count; 31: } 32: }
Notes:
There are at most 50 possibilities for side 1, 49 for side 2, and 48 for side 3. This give 117,600 combinations, small enough for a brute force solution.
The nested for loops work through each possible combination. Inside the loops, we check so see if the sides form a legal triangle. This is true if and only if the length of any two sides is greater than the third.
If it's a valid triangle, increment count. Then return count at the end.
No comments:
Post a Comment