OrAndSum
SRM 724 · 2017-11-27 · by cgy4ever
SRM 724 · 2017-11-27 · by cgy4ever · Math
Problem Statement
Problem Statement
You are given two long[] s: pairOr and pairSum.
Each of these arrays will contain n non-negative integers.
Determine whether it is possible to construct a sequence x[0], ..., x[n] of nonnegative integers with the following properties:
Note that the sequence x should contain n+1 elements: one more than the length of each of the given arrays.
Return "Possible" if we can find at least one such sequence x, and "Impossible" if not.
Determine whether it is possible to construct a sequence x[0], ..., x[n] of nonnegative integers with the following properties:
- for each i between 0 and n-1, inclusive, x[i] or x[i+1] = pairOr[i]
- for each i between 0 and n-1, inclusive, x[i] + x[i+1] = pairSum[i]
Note that the sequence x should contain n+1 elements: one more than the length of each of the given arrays.
Return "Possible" if we can find at least one such sequence x, and "Impossible" if not.
Constraints
- pairOr will contain between 1 and 50 elements, inclusive.
- pairOr and pairSum will contain the same number of elements.
- Each element in pairOr will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
- Each element in pairSum will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
Examples
0)
{7}
{11}
Returns: "Possible"
One of the solutions is {5,6}.
1)
{11}
{7}
Returns: "Impossible"
The sum of two numbers will always be greater than or equal to their bitwise or.
2)
{3,3,7,5,7}
{3,5,7,9,11}
Returns: "Possible"
One of the solutions is {1,2,3,4,5,6}.
3)
{1,100,1000}
{100,1000,10000}
Returns: "Impossible"
4)
{261208776456074191,261208776456074191,261208776456074191}
{333333333333333333,333333333333333333,333333333333333333}
Returns: "Possible"
Submissions are judged against all 151 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class OrAndSum with a public method string isPossible(vector<long long> pairOr, vector<long long> pairSum) · 151 test cases · 2 s / 256 MB per case