Best Permutation (Codeforces 1728B)
Tags: Greedy, constructive algorithms

Let's define the value of the permutation $$$p$$$ of $$$n$$$ integers $$$1$$$, $$$2$$$, ..., $$$n$$$ (a permutation is an array where each element from $$$1$$$ to $$$n$$$ occurs exactly once) as follows:  initially, an integer variable $$$x$$$ is equal to $$$0$$$;  if $$$x < p_1$$$, then add $$$p_1$$$ to $$$x$$$ (set $$$x = x + p_1$$$), otherwise assign $$$0$$$ to $$$x$$$;  if $$$x < p_2$$$, then add $$$p_2$$$ to $$$x$$$ (set $$$x = x + p_2$$$), otherwise assign $$$0$$$ to $$$x$$$;  ...  if $$$x < p_n$$$, then add $$$p_n$$$ to $$$x$$$ (set $$$x = x + p_n$$$), otherwise assign $$$0$$$ to $$$x$$$;  the value of the permutation is $$$x$$$ at the end of this process. For example, for $$$p = [4, 5, 1, 2, 3, 6]$$$, the value of $$$x$$$ changes as follows: $$$0, 4, 9, 0, 2, 5, 11$$$, so the value of the permutation is $$$11$$$.You are given an integer $$$n$$$. Find a permutation $$$p$$$ of size $$$n$$$ with the maximum possible value among all permutations of size $$$n$$$. If there are several such permutations, you can print any of them.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 97$$$) — the number of test cases.The only line of each test case contains one integer $$$n$$$ ($$$4 \le n \le 100$$$).

Output: For each test case, print $$$n$$$ integers — the permutation $$$p$$$ of size $$$n$$$ with the maximum possible value among all permutations of size $$$n$$$.


Sample Inputs:
3
4
5
6

Sample Outputs:
2 1 3 4
1 2 3 4 5
4 5 1 2 3 6

Solution (Python):
for n in [*map(int, open(0))][1:]:
    (*r,) = range(1, n + 1)
    r[n % 2:n - 2] = r[n % 2:n - 2][::-1]
    print(*r)

Solution (Python):
for _ in range(int(input())):
    a = int(input())
    c = ''
    if a % 2 == 1:
        for i in range(1, a):
            if i != 1 and i != a - 1:
                c += str(a - i) + ' '
            else:
                c += str(i) + ' '
        c += str(a) + ' '
    else:
        for i in range(2, a):
            c += str(a - i) + ' '
        c += str(a - 1) + ' ' + str(a) + ' '
    print(c)

Solution (Python):
class Solution:

    def __init__(self):
        pass

    def solve(self):
        t = int(input())
        result = []
        for i in range(t):
            n = int(input())
            string = ''
            if n % 2 == 0:
                for j in range(n - 2, 0, -1):
                    string += '{} '.format(j)
            else:
                for j in range(n - 2, 3, -1):
                    string += '{} '.format(j)
                string += '1 3 2 '
            string += '{} '.format(n - 1)
            string += '{} '.format(n)
            result.append(string)
        for x in result:
            print(x)
if __name__ == '__main__':
    sol = Solution()
    sol.solve()