TriCount

SRM 284 · 2006-01-21 · by dgoodman

SRM 284 · 2006-01-21 · by dgoodman · Math

Show categories

Class Name: TriCount

Return Type: int

Method Name: count

Arg Types: (int, int)

Problem Statement

We are interested in triangles that have integer length sides, all of which are between minLength and maxLength, inclusive. How many such triangles are there?

Two triangles differ if they have a different collection of side lengths, ignoring order. Triangles with side lengths {2,3,4} and {4,3,5} differ, but {2,3,4} and {4,2,3} do not. We are only interested in proper triangles; the sum of the two smallest sides of a proper triangle must be strictly greater than the length of the biggest side.

Create a class TriCount that contains a method count that is given ints minLength and maxLength and returns the number of different proper triangles whose sides all have lengths between minLength and maxLength, inclusive. If there are more than 1,000,000,000 return -1.

Constraints

minLength is between 1 and 1,000,000, inclusive.
maxLength is between minLength and 1,000,000, inclusive.

Examples

1
2
Returns: 3

The proper triangles with side lengths between 1 and 2 inclusive are {1,1,1} and {2,2,2} and {1,2,2}.

9
10
Returns: 4

9,9,9 and 10,10,10 and 9,9,10 and 9,10,10

1
1000000
Returns: -1

There are VERY many triangles with lengths in this range.

19
1000
Returns: 83540657

52
2290
Returns: 999746335

Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TriCount with a public method int count(int minLength, int maxLength) · 63 test cases · 2 s / 256 MB per case