Connection Status:
Competition Arena > AqaAsadiPlays

AqaAsadiPlays

SRM 787 · 2020-06-17 · by a.poorakhavan

SRM 787 · 2020-06-17 · by a.poorakhavan · Math
Class Name: AqaAsadiPlays
Return Type: int
Method Name: getMin
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Aqa Asadi is forming a Ninja INOI team from his students. You are given the power of each student in the int[] A. It is known that the power of a team is equal to the greatest common divisor (GCD) of the team members' powers.

A student is unhappy if they are not on the team but they feel that they are good enough to be selected for the team. To prevent unhappy students, the power of the Ninja team must be strictly bigger than the power of each individual student who is not included in the team.

The Ninja team cannot be empty and it cannot contain all the students.

Compute and return the size of the largest valid Ninja team. If there is no suitable Ninja team, return -1 instead.

Constraints

  • The length of A will be between 1 and 100, inclusive.
  • Elements of A will be between 1 and 1000000000 (10^9), inclusive.
Examples
0)
{6, 1, 4}
Returns: 2

Aqa Asadi can select the first and the last student. The power of the team will be GCD(6,4) = 2. The power of the student who was not selected is 1, which is strictly less than the power of the team. (Selecting only the first student would also be valid, but remember that we are looking for the largest possible team.)

1)
{4, 4, 1, 3, 2}
Returns: 2

The only valid solution is a team with power 4 consisting of the first two students.

2)
{2, 8, 3, 12, 16}
Returns: 3
3)
{3, 7, 1, 9, 6, 8, 7, 7, 4, 3, 1, 8, 1, 3, 5, 2, 8, 4, 2, 1, 9, 9,
       9, 3, 8, 5, 2, 3, 6, 1, 4, 1, 2, 5, 9, 7, 9, 6, 6, 8, 9, 6, 3, 3,
       2, 8, 4, 4, 2, 2, 3, 4, 4, 7, 2, 7, 1, 3, 8, 3, 5, 9, 2, 1, 3, 7,
       9, 2, 6, 5, 8, 4, 2, 3, 8, 4, 3, 9, 5, 9, 8, 4, 6, 9, 1, 4, 4, 7,
       4, 6, 4, 3, 3, 3, 3, 5, 1, 4, 8, 3}
Returns: 12
4)
{118714243, 503288602, 461707287, 147402629, 180567538, 832123448,
       238797439, 847726340, 827432795, 721037412, 975707380, 739972034,
       507979857, 568196047, 400098373,  34349482, 594577208, 241603567,
       436035986, 568187308, 931725476,   9074529, 657493086, 442545273,
        31282974, 452083746, 656237216, 222067571, 559490603, 944722004,
       828977181, 960222070, 531148792, 607946722, 170285798, 107803105,
       889184742, 161776246, 592676908, 187954112, 109947349, 745295719,
       151295847, 775455552, 863945134, 793444191, 295256623, 165286563,
       277873033,  79275071, 105127174, 775680779,  13143475, 775798568,
       676112029, 237568652, 858806156, 258625473, 153991682, 698457479,
       806584913, 103529603, 461626146, 914007659, 750116841, 183035066,
       642718041, 454662926, 212029977, 121127210, 922076889, 203132500,
       813908653, 377033569, 533574838, 244148116, 433294140, 657638879,
       653772139, 530088430, 301151292, 219753698, 759029330, 974356474,
       863443703, 922548333, 318421643, 837355315, 541836999, 681986445,
       349545051, 851434796, 788423650, 182240785, 887740828, 671912945,
       300908242, 944129157, 924844574, 393398967}
Returns: 1

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

Coding Area

Language: C++17 · define a public class AqaAsadiPlays with a public method int getMin(vector<int> A) · 61 test cases · 2 s / 256 MB per case

Submitting as anonymous