KPlanetaryAlignment
SRM 414 · 2008-08-16 · by StevieT
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.
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.
{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.
{-20,10,-40,40}
2
9
11
Returns: 1
{-1,-2,1,2,3}
2
0
50000000
Returns: 433333335
Quite large answer (possibly max).
Submissions are judged against all 78 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class KPlanetaryAlignment with a public method int number(vector<int> periods, int k, int T1, int T2) · 78 test cases · 2 s / 256 MB per case