KPlanetaryAlignment | Topcoder Archive

Problem Statement

A particular star system consists of a single star, with N planets orbiting it. Each planetary orbit is a perfect circle of distinct radius centered on the star and all orbits lie in the same 2-D plane. The planets move along their circular paths with constant speed and planet i completes 1 full orbit in the time given by the absolute value of periods[i]. periods[i] will be positive if planet i orbits clockwise and negative if it orbits counter-clockwise. A k-planetary alignment occurs when an infinite straight line exists, passing through the center of the star and through the centers of at least k of the planets. A N-planetary alignment occurs at time T = 0, i.e., all the planets lie in a line at this time (see notes for clarification). Return the number of distinct times between T1 and T2, inclusive, when a k-planetary alignment occurs.

Definition

Class:: KPlanetaryAlignment
Method:: number
Parameters:: int[], int, int, int
Returns:: int
Method signature:: int number(int[] periods, int k, int T1, int T2)
(be sure your method is public)

Notes

The constraints ensure the return value will fit in a signed 32-bit integer.
Alignments can occur with the planets either on the same side of the star or diametrically opposite each other.
The configuration of the planets at T = 0 (i.e., whether the planets are all on the same side, or some are diametrically opposite) makes no difference to the answer.

Constraints

periods will contain between 2 and 5 elements, inclusive.
Each element of periods will be a non-zero integer between -100 and 100, inclusive.
The elements of periods will be distinct.
k will be between 2 and the number of elements in periods, inclusive.
T2 will be between 0 and 50,000,000 (5 * 10^7), inclusive.
T1 will be between 0 and T2, inclusive.

Examples

```
{8,40}
```
```
2
```
```
0
```
```
20
```
```
Returns: 5
```
Here, the first planet is rotating 5 times as quickly as the second. Ater 5 seconds, the first will have completed 5/8 of an orbit, while the second will have completed 5/40 = 1/8 of an orbit. They are therefore diametrically opposite and this is the first 2-alignment after time 0. Further 2-alignments happen at T = 10, 15 and 20.
```
{8,24,40}
```
```
2
```
```
0
```
```
20
```
```
Returns: 8
```
With an additional planet, 2-alignments happen at T = 0, 5, 6, 10, 12, 15, 18, 20.
```
{8,24,40}
```
```
3
```
```
0
```
```
100
```
```
Returns: 4
```
3-alignments of the same set of planets happen at T = 0, 30, 60, 90.
```
{-10,10}
```
```
2
```
```
2
```
```
26
```
```
Returns: 10
```
Now that the planets are rotating in opposite directions, 2-alignments occur every 2 1/2 seconds.
```
{-1,2,3,4,5}
```
```
3
```
```
10000
```
```
50000
```
```
Returns: 53333
```
```
{-1,1}
```
```
2
```
```
0
```
```
50000
```
```
Returns: 200001
```
```
{-2,91,87,77,71}
```
```
4
```
```
0
```
```
50000000
```
```
Returns: 1471
```

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.