FoxPlusMinus | Topcoder Archive

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.

Definition

Class:: FoxPlusMinus
Method:: maximize
Parameters:: int[], int
Returns:: int[]
Method signature:: int[] maximize(int[] first, int N)
(be sure your method is public)

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}

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

{2, 7, -1, 8, -2, -8}

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

{-10, -20, -30}

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

{1, 2, 4, 9, 7, 3}

Returns: {3, 4, 2, 7, 1, 9 }

{-4112039, 51143992, 941422315, -153492958, 499218832, 543599293, 132059490, -434243951,
 -95819234, 1552938, -857192847, 481950390, 401099286, 71482395, -711450593, 8101919}

884142312

Returns: {51143992, 8101919, 71482395, 1552938, 132059490, -4112039, 401099286, -95819234, 481950390, -153492958, 499218832, -434243951, 543599293, -711450593, 941422315, -857192847 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.