FoxPlusMinus

SRM 552 · 2012-06-05 · by wrong

SRM 552 · 2012-06-05 · by wrong · Simple Math, Simple Search, Iteration

Show categories

Class Name: FoxPlusMinus

Return Type: int[]

Method Name: maximize

Arg Types: (vector<int>, int)

Problem Statement

Fox Jiro is interested in sequences of intetegers. Today he considers the sequence given to you as the int[] first. Let K be the number of elements of first. Jiro chooses some permutation of first. Let's call this permutation F. An infinite sequence of integers A is defined as follows:

for all i, 0 <= i < K, A[i] = F[i].
Otherwise, A[i] = A[i-K] - A[i-K+1] + ... + (-1)^(K-1) * A[i-1].

In addition to first, Jiro has a int N. His goal is to maximize the value of A[N]. Return a int[] containing the best choice of F. If there are multiple permutations of first maximizing the value of A[N], return the lexicographically smallest one.

Notes

A int[] A is lexicographically smaller than a int[] B if A contains a smaller number at the first index where they differ.

Constraints

first will contain between 1 and 50 elements, inclusive.
Each element of first will be between -1,000,000,000 and 1,000,000,000, inclusive.
N will be between 0 and 1,000,000,000, inclusive.

Examples

{1, 2}
2
Returns: {2, 1 }

A[2] will be 1 if F = {2, 1}, and it will be -1 if F = {1, 2}.

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

{3, 1, 2} also maximizes A[3] but {2, 1, 3} is lexicographically smaller.

{-3, 1, -4, 1, -5, 9, -2}
10
Returns: {-5, -4, 9, -3, -2, 1, 1 }

{2, 7, -1, 8, -2, -8}
10
Returns: {2, -1, 7, -2, 8, -8 }

{-10, -20, -30}
1
Returns: {-30, -10, -20 }

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

Coding Area

Language: C++17 · define a public class FoxPlusMinus with a public method vector<int> maximize(vector<int> first, int N) · 91 test cases · 2 s / 256 MB per case