DivisibleSetDiv1

SRM 697 · 2016-07-09 · by Arterm

SRM 697 · 2016-07-09 · by Arterm · Greedy, Sorting

Show categories

Class Name: DivisibleSetDiv1

Return Type: String

Method Name: isPossible

Arg Types: (vector<int>)

Problem Statement

You are given a int[] b containing a sequence of n positive integers: b[0], ..., b[n-1]. We are now looking for another sequence a = {a[0], ..., a[n-1]}. This sequence should have the following properties:

The elements of the sequence a should be distinct.
Each a[i] should be an integer greater than 1.
For each i, the value a[i]^b[i] (that is, a[i] to the power b[i]) should be divisible by p[i], where p[i] is the product of all other elements of a. (I.e. p[i] = a[0]*a[1]*...*a[i-1]*a[i+1]*...*a[n-1].)

Determine whether there is at least one sequence with the desired properties. Return "Possible" (quotes for clarity) if such a sequence exists and "Impossible" otherwise.

Constraints

b will contain between 2 and 50 elements, inclusive.
Each element in b will be between 1 and 10, inclusive.

Examples

{2,1}
Returns: "Possible"

Here, we have the following requirements: The values a[0] and a[1] should be distinct positive integers, both greater than 1. The value a[0]^2 should be divisible by a[1]. The value a[1]^1 should be divisible by a[0]. One sequence with the above properties is the sequence a = {2, 4}.

{1,1}
Returns: "Impossible"

In this test case the requirements imply that a[0] must be divisible by a[1] and vice versa. This is possible only if a[0] = a[1]. However, the elements of a must be distinct, so there is no valid sequence.

{7, 7, 7}
Returns: "Possible"

For example, a = {12, 54, 18}.

{6,7,5,2}
Returns: "Possible"

{1,7,10,7,8}
Returns: "Possible"

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

Coding Area

Language: C++17 · define a public class DivisibleSetDiv1 with a public method string isPossible(vector<int> b) · 159 test cases · 2 s / 256 MB per case