DivisibleSetDiv2

SRM 697 · 2016-07-09 · by Arterm

SRM 697 · 2016-07-09 · by Arterm · Greedy, Simple Math

Show categories

Class Name: DivisibleSetDiv2

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[0], ..., a[n-1]. This sequence should have the following properties:

Each a[i] should be a number of the form 2^x[i] where x[i] is some positive integer. In other words, each a[i] is one of the numbers 2, 4, 8, 16, ...
For each i, the value a[i]^b[i] (that is, a[i] to the power b[i]) should be divisible by P, where P is the product of all a[i].

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 1 and 50 elements, inclusive.
Each element in b will be between 1 and 10, inclusive.

Examples

{3,2}
Returns: "Possible"

One valid sequence is the sequence {2, 2}. That is, a[0] = a[1] = 2. Clearly, each a[i] is a power of two not smaller than 2. The product of all a[i] is 2*2 = 4. Both a[0]^b[0] = 2^3 = 8 and a[1]^b[1] = 2^2 = 4 are divisible by 4.

{3,3,3}
Returns: "Possible"

Here, one valid sequence is {2, 2, 2}.

{1,10}
Returns: "Impossible"

Suppose that a[0] = x and a[1] = y. The value a[0]^b[0] = x^1 should be divisible by x*y. This is only possible for y = 1. However, 1 is not a positive power of two, so we cannot have a[1] = 1.

{5,3,9,7}
Returns: "Possible"

{1}
Returns: "Possible"

27)

{2, 3, 10}
Returns: "Possible"

One valid sequence is {8, 4, 2}.

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

Coding Area

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