Xscoregame
SRM 709 · 2016-12-07 · by subscriber
SRM 709 · 2016-12-07 · by subscriber · Dynamic Programming
Problem Statement
Problem Statement
You have an array of integers: the int[] A.
When you give the array to Hero, he will execute the following steps:
- At the beginning, he will set the variable X to zero.
- For each element Y of A, in the given order, he will set X to (X + (X xor Y)).
- He will announce the final value of the variable X.
Constraints
- A will contain between 1 and 15 elements, inclusive.
- Each element in A will be between 0 and 50, inclusive.
Examples
0)
{1,2,3}
Returns: 12
An optimal solution is to rearrange A into the order {3, 1, 2}. Given this array, Hero will perform the following steps: He will set X to zero. Then, he will set X to (0 + (0 xor 3)) = 3. Then, he will set X to (3 + (3 xor 1)) = 5. Finally, he will set X to (5 + (5 xor 2)) = 12, and he will announce the value 12.
1)
{10,0,0,0}
Returns: 80
Here an optimal solution is to leave the array in the original order. The variable X will have the values 0, 10, 20, 40, and finally 80.
2)
{1,1,1,1,1,1}
Returns: 1
3)
{1,0,1,0,1,0,1,0}
Returns: 170
4)
{50,0,1,0,1,0,1,0,1,0,1,0,1,0,1}
Returns: 830122
Submissions are judged against all 160 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Xscoregame with a public method int getscore(vector<int> A) · 160 test cases · 2 s / 256 MB per case