AstronomicalRecords
SRM 594 · 2013-06-25 · by cgy4ever
SRM 594 · 2013-06-25 · by cgy4ever · Dynamic Programming
Problem Statement
Problem Statement
Fox Ciel found two astronomical records.
They both describe the same solar system.
Each planet in the system can be characterized by two parameters each being a positive number: planet's size and the distance at which it orbits the sun.
All orbital distances are pairwise distinct, but sizes of some planets may be the same.
The first record is aint[] A with x elements.
These elements give the relative sizes of some x planets in the solar system.
Formally, the sizes of those planets have the ratio A[0] : A[1] : ... : A[x-1].
The planets described by A are ordered by their distance from the sun.
(That is, earlier elements of A correspond to planets that are closer to the sun.)
The second record is aint[] B with y elements.
These elements give the relative sizes of some y planets in the solar system.
Formally, the sizes of those planets have the ratio B[0] : B[1] : ... : B[y-1].
The planets described by B are ordered by their distance from the sun.
Note that the planets considered by a record do not have to be consecutive. For example, if a solar system contains the planets P, Q, R, S, T, and U, it is possible that the first record compares P, R, and S, and the second record compares Q, R, T, and U.
We assume that both records are correct. Return the smallest possible total number of planets in the solar system.
The first record is a
The second record is a
Note that the planets considered by a record do not have to be consecutive. For example, if a solar system contains the planets P, Q, R, S, T, and U, it is possible that the first record compares P, R, and S, and the second record compares Q, R, T, and U.
We assume that both records are correct. Return the smallest possible total number of planets in the solar system.
Constraints
- A will contain between 2 and 50 elements, inclusive.
- B will contain between 2 and 50 elements, inclusive.
- Each element in A will be between 1 and 1,000,000,000, inclusive.
- Each element in B will be between 1 and 1,000,000,000, inclusive.
Examples
0)
{1,2,1,2,1}
{2,1,2,1,2}
Returns: 6
There have to be at least 5 planets, because each record compares 5 of them. There cannot be exactly 5 planets, because the first one would have to be both smaller than and larger than the second one. (Their ratio would have to be both 1:2 and 2:1, which is impossible.) There can be exactly 6 planets with relative sizes 1,2,1,2,1,2.
1)
{1,2,3,4}
{2,4,6,8}
Returns: 4
There can be only 4 planets because 1:2:3:4 = 2:4:6:8.
2)
{2,3,2,3,2,3,2}
{600,700,600,700,600,700,600}
Returns: 10
3)
{1,2,3,4,5,6,7,8,9}
{6,7,8,9,10,11,12}
Returns: 12
4)
{100000000,200000000}
{200000000,100000000}
Returns: 3
Submissions are judged against all 205 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class AstronomicalRecords with a public method int minimalPlanets(vector<int> A, vector<int> B) · 205 test cases · 2 s / 256 MB per case