PROBLEM STATEMENT
Old McDonald has a farm, with many chickens. He notices that for whatever
reason, the chickens in triangle shaped cages generally produce more eggs. So
Old McDonald has decided to make all his cages in the shape of right triangles.
However, when cutting the wood to make the cage, Old McDonald realizes it is
easier if he only has to deal with integers - so he has decided to make all
lengths of the triangles positive integers (natural numbers). Remembering back
to junior-high, Old McDonald uses his knowledge of Pythagorean triples to
decide on the exact size of the cage. Given an area the chickens need in order
to produce eggs, compute the minimum perimeter of a right triangle with
integral sides which has an area greater than or equal to the given area.
A triangle with sides A, B, and C (A,B < C) will be a right triangle if and
only if A*A + B*B = C*C. We compute such A,B, and C using the following method:
a) Pick numbers m,n such that 1 <= m < n.
b) Let A = n*n - m*m, B = 2*m*n, C = m*m+n*n.
c) Simple algebra shows that A*A + B*B = C*C.
For example: let n = 2, m = 1.
A = n*n - m*m = 3
B = 2*m*n = 4
C = n*n + m*m = 5.
This is the well known 3-4-5 right triangle.
Remember that the area of the triangle can be computed (1/2)*A*B, and the
perimeter is A+B+C. Return the minimum possible value for A+B+C where
(1/2)*A*B >= area. See examples.
DEFINITION
Class Name: RtTriangle
Method Name: getPerim
Parameters: int
Returns: int
Method Signature (be sure your method is public): int getPerim(int area);
NOTES
- When generating the triples, make sure that n > m, and m >= 1. Otherwise you
may get non-positive lengths for the sides.
- When generating the triples, the numbers get quite large very fast. To get
the correct answer, it will not be necessary to check values beyond n = 50.
TopCoder will ensure that:
- area will be between 1 and 1,000,000 (inclusive).
EXAMPLES
1. area = 6
Using n = 2, m = 1, we can get a 3-4-5 triangle, with area (1/2)*3*4 = 6.
Obviously, there are other triangles with an area >= 6, but this is the one
with the least perimeter (3+4+5=12). Return 12.
2. area = 10
Using n = 2, m = 1 is not enough. Try n = 3, m = 1 which yields a 6-8-10
triangle. The area is 24, so that's definitely enough and the perimeter is
also 24. Looking at other possibilities, it is clear to see this is the best
triangle for an area of 10. Return 24.
3. area = 100
Using n = 5, m = 1 gives a 10-24-26 triangle; using n = 5, m = 2 gives a
20-21-29 triangle; using n = 5, m = 3 gives a 16-30-34 triangle; using n = 5, m
= 4 gives a 9-40-41 triangle. All of these have enough area (at least 100),
but the 10-24-26 has the smallest perimeter (60). Using bigger values of n
will make the perimeter get very large, so a 10-24-26 triangle is our best
choice. Return 60.