ObtuseTrianglesDiv1 | Topcoder Archive

Problem Statement

An obtuse triangle is a triangle in which one of the internal angles has strictly more than 90 degrees. Equivalently, a triangle with side lengths a ≤ b ≤ c is obtuse if and only if c^2 > a^2 + b^2.

You have 3*n sticks: for each integer x between a and a+3*n-1, inclusive, you have one stick of length x. You want to use these 3*n sticks to build n disjoint obtuse triangles. (Hence, each stick has to be used as a side of exactly one of the triangles.)

You are given the ints a and n. Find out whether it is possible to construct n disjoint obtuse triangles, and if it is, construct one such set. If there is no solution, return an empty long[]. Otherwise, return a long[] constructed as follows:

Suppose (x₁, y₁, z₁), (x₂, y₂, z₂), ..., (x_n, y_n, z_n) is your way to construct n obtuse triangles. Then, return the following long[]:
{
x₁*10⁸ + y₁*10⁴ + z₁,
x₂*10⁸ + y₂*10⁴ + z₂,
...,
x_n*10⁸ + y_n*10⁴ + z_n
}.

If there are many ways to construct n obtuse triangles while using each stick exactly once, you may choose any one of them. Within each triangle, the order of the three sticks in your answer does not matter.

Definition

Class:: ObtuseTrianglesDiv1
Method:: findObtuseTriangles
Parameters:: int, int
Returns:: long[]
Method signature:: long[] findObtuseTriangles(int a, int n)
(be sure your method is public)

Constraints

a will be between 1 and 10, inclusive.
n will be between 1 and 500, inclusive.

Examples

```
2
```
```
1
```
```
Returns: {200030004 }
```
Ordering of the three sticks within a triangle does not matter, so {300040002} is another correct answer.
```
3
```
```
1
```
```
Returns: { }
```
Using three sticks of length 3, 4, and 5, respectively, we can only create a right triangle, but not an obtuse triangle.
```
2
```
```
2
```
```
Returns: {200040005, 300070006 }
```
We have sticks of length 2, 3, 4, 5, 6, and 7, respectively. The return value shown above describes the obtuse triangles (2,4,5) and (3,6,7). Ordering of the elements in the returned array does not matter, so {300070006, 200050004} is another correct answer.

Returns: {1000160025, 1100170024, 1200190023, 1300210026, 1400150022, 1800200027 }

Returns: {800130020, 900140019, 1000170021, 1100120018, 1500160022 }

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.