PROBLEM STATEMENT
The prince has just been introduced to primitive pythagorean triplets.
A primitive pythagorean triplet (a, b, c) is a triplet satisfying the following properties:
a, b and c are integers
a^2 + b^2 = c^2
The greatest common divisor of a and b is 1
The prince is not very fond of mathematics. The king is trying to make mathematics fun for his son
(the prince). So, the king decides to make as many toys as possible which are triangular in shape
having sides (a, b, c) where (a, b, c) form a primitive pythogorean triplet. The wooden framework
of the two shorter legs of the toy give the toy its shape and prevent it from breaking, hence each
toy with sides of length (a, b, c) must have one wooden stick of length a and one of length b. The
third side of length c is not made of wood, and therefore the king does not need a wooden stick
for it.
You are given a vector stick. Concatenate the elements of stick to get a single-space
separated list of the lengths of available sticks. The king is a very loving father and would like
to make the toys with his own hands. However, he is not skilled enough to cut the sticks, so he
must use them in the sizes they are available. Return the maximum possible number of toys the king
can make using these sticks.
DEFINITION
Class:PythTriplets
Method:findMax
Parameters:vector
Returns:int
Method signature:int findMax(vector stick)
NOTES
-An integer may be listed multiple times in the string formed by the concatenation of stick . If
an integer n is listed k times, then the king has exactly k sticks of length n available with him.
CONSTRAINTS
-stick will contain between 1 and 50 elements, inclusive.
-Each element of stick will contain between 1 and 50 characters, inclusive.
-When concatenated, stick will represent a single-space separated list of N integers, where N is
between 1 and 200 inclusive.
-Each listed integer will be between 1 and 999999, inclusive.
-Listed integers will not have leading zeroes.
EXAMPLES
0)
{"3 4 4 3 11 5 12 9 4"}
Returns: 3
(3, 4, 5) and (5, 12, 13) are primitive pythagorean triplets. Hence, there are three disjoint
pairs (a, b) - (3, 4), (3, 4) and (5, 12).
1)
{"20 21 3021 220"}
Returns: 2
Possible pairs (a, b) are (20, 21), (21, 220) and (220, 3021). The maximum number of disjoint
pairs is 2. Namely, (20, 21) and (220, 3021).
2)
{"28 19", "5 1035 21412 37995"}
Returns: 2
Make sure you concatenate the elements of stick.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.