1859C.md (1856B)
1 Source: https://codeforces.com/problemset/problem/1859/C 2 3 C. Another Permutation Problem 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Andrey is just starting to come up with problems, and it's difficult for him. That's why he came up with a strange problem about permutations$^{\dagger}$ and asks you to solve it. Can you do it? 22 23 Let's call the cost of a permutation $p$ of length $n$ the value of the expression: 24 25 $(\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)$. 26 27 Find the maximum cost among all permutations of length $n$. 28 29 $^{\dagger}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 30 31 Input 32 33 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 30$) — the number of test cases. The description of the test cases follows. 34 35 The only line of each test case contains a single integer $n$ ($2 \le n \le 250$) — the length of the permutation. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $500$. 38 39 Output 40 41 For each test case, output a single integer — the maximum cost among all permutations of length $n$. 42 43 Example 44 45 Input 46 47 ``` 48 5 49 50 2 51 52 4 53 54 3 55 56 10 57 58 20 59 ``` 60 61 Output 62 63 ``` 64 2 65 17 66 7 67 303 68 2529 69 ``` 70 71 Note 72 73 In the first test case, the permutation with the maximum cost is $[2, 1]$. The cost is equal to $2 \cdot 1 + 1 \cdot 2 - \max (2 \cdot 1, 1 \cdot 2)= 2 + 2 - 2 = 2$. 74 75 In the second test case, the permutation with the maximum cost is $[1, 2, 4, 3]$. The cost is equal to $1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3 + 3 \cdot 4 - 4 \cdot 3 = 17$.