PythTriplets | Topcoder Archive

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 String[] 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:: String[]
Returns:: int
Method signature:: int findMax(String[] stick)
(be sure your method is public)

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

```
{"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).
```
{"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).
```
{"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)2024, TopCoder, Inc. All rights reserved.