310609: CF1859C. Another Permutation Problem

Memory Limit：256 MB Time Limit：3 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

C. Another Permutation Problemtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Let's call the cost of a permutation $p$ of length $n$ the value of the expression:

$(\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)$.

Find the maximum cost among all permutations of length $n$.

$^{\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).

Input

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.

The only line of each test case contains a single integer $n$ ($2 \le n \le 250$) — the length of the permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$.

Output

For each test case, output a single integer — the maximum cost among all permutations of length $n$.

ExampleInput
5
2
4
3
10
20
Output
2
17
7
303
2529
Note

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$.

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$.

Output

题目大意：
C. 另一个排列问题

安德烈刚开始出题，对他来说这很困难。因此他想出了一个关于排列的奇怪问题，并请你解决。你能做到吗？

我们将长度为n的排列p的**成本**定义为表达式：

$$
(\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)
$$

的值。找出长度为n的所有排列中最大的成本。

**输入数据格式**：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤30）——测试用例的数量。接下来是测试用例的描述。

每个测试用例只有一行，包含一个整数n（2≤n≤250）——排列的长度。

保证所有测试用例的n之和不超过500。

**输出数据格式**：
对于每个测试用例，输出一个整数——长度为n的所有排列中最大的成本。

**示例**：
输入
```
5
2
4
3
10
20
```
输出
```
2
17
7
303
2529
```

**注意**：
- 在第一个测试用例中，成本最高的排列是[2, 1]。成本等于$2 \cdot 1 + 1 \cdot 2 - \max(2 \cdot 1, 1 \cdot 2) = 2 + 2 - 2 = 2$。
- 在第二个测试用例中，成本最高的排列是[1, 2, 4, 3]。成本等于$1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3 + 3 \cdot 4 - 4 \cdot 3 = 17$。题目大意： C. 另一个排列问题 安德烈刚开始出题，对他来说这很困难。因此他想出了一个关于排列的奇怪问题，并请你解决。你能做到吗？ 我们将长度为n的排列p的**成本**定义为表达式： $$ (\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j) $$ 的值。找出长度为n的所有排列中最大的成本。 **输入数据格式**： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤30）——测试用例的数量。接下来是测试用例的描述。 每个测试用例只有一行，包含一个整数n（2≤n≤250）——排列的长度。 保证所有测试用例的n之和不超过500。 **输出数据格式**： 对于每个测试用例，输出一个整数——长度为n的所有排列中最大的成本。 **示例**： 输入 ``` 5 2 4 3 10 20 ``` 输出 ``` 2 17 7 303 2529 ``` **注意**： - 在第一个测试用例中，成本最高的排列是[2, 1]。成本等于$2 \cdot 1 + 1 \cdot 2 - \max(2 \cdot 1, 1 \cdot 2) = 2 + 2 - 2 = 2$。 - 在第二个测试用例中，成本最高的排列是[1, 2, 4, 3]。成本等于$1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3 + 3 \cdot 4 - 4 \cdot 3 = 17$。

Source/Category

加入题单

上一题 下一题 算法标签：