Connection Status:
Competition Arena > RightTriangle

RightTriangle

SRM 473 · 2009-11-12 · by misof

SRM 473 · 2009-11-12 · by misof · Math, Search
Class Name: RightTriangle
Return Type: long
Method Name: triangleCount
Arg Types: (int, int, int, int, int)
Problem Statement

Problem Statement

Consider a circle in the plane.

You are given an int places. This is the number of places that are equally spaced along the perimeter of the circle, i.e., the distance between any two consecutive places is equal. The places are numbered 0 to places-1 in clockwise order, starting at an arbitrary place.

We will now draw red points in some of the places. The number of red points is given as an int points. As the number of points may be large, we will generate them using a simple process that is described below.

Finally, once all points are generated, your task is to find and return the number of right triangles that have all three vertices in red points.

To generate the points, you are given three ints a, b, and c. For n = 0, 1, 2, 3, ..., points-1, execute the following steps:

  • Compute P[n] = (a*n*n + b*n + c) modulo places.
  • Starting at P[n], find the first place in the clockwise direction that does not contain a red point.
  • Put a red point onto that place.

Notes

  • A right triangle is a triangle with non-zero area in which one of the angles is exactly 90 degrees.
  • For any valid input the answer fits into a long (i.e., a signed 64-bit integer variable).

Constraints

  • places will be between 1 and 1,000,000, inclusive.
  • points will be between 0 and 100,000, inclusive.
  • points will not be greater than places.
  • a will be between 0 and 1,000,000, inclusive.
  • b will be between 0 and 1,000,000, inclusive.
  • c will be between 0 and 1,000,000, inclusive.
Examples
0)
9
3
0
3
0
Returns: 0

The points are placed on places 0, 3, and 6. The resulting triangle is not a right triangle (in fact, it is equilateral).

1)
40
3
5
0
0
Returns: 1

This time the red points are on places 0, 5, and 20. The only triangle determined by these points is a right triangle.

2)
4
4
16
24
17
Returns: 4

This time the formula for the next place always gives the output 1. Hence the points are placed on places 1, 2, 3, and 0, in this order. Each of the four triangles determined by these points is a right triangle.

3)
1000000
47000
0
2
5
Returns: 0

An awful lot of obtuse triangles.

4)
100000
100000
0
0
987654
Returns: 4999900000
9)
200000
700
123456
789012
345678
Returns: 6980

Watch out for integer overflow when computing P[n].

11)
200000
100000
800000
100000
77777
Returns: 4999900000

similar to #10, but a is positive (is somebody compares just with 0, it fails)

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

Coding Area

Language: C++17 · define a public class RightTriangle with a public method long long triangleCount(int places, int points, int a, int b, int c) · 137 test cases · 2 s / 256 MB per case

Submitting as anonymous