Problem Statement:
A DOTA game has N heroes, each with a distinct rank from [1..N]. In DOTA every formation is characterized as a permutation [1...N] of ranks of players. A formation is Imba when the sum of ranks of every two consecutive players is less than or equal to (N+1). Given N, you are to print the lexicographically smallest permutation of ranks [1...N] that makes the formation Imba.
Input Format
The first line will contain an integer T, i.e. the number of the test cases followed by T lines, each containing the value of N.
Constraints
- \$1 \le T \le 5\$
- \$2 \le N \le 105\$
Output Format
\$T\$ lines each containing the permutation; the numbers in each line should be seperated by a single space.
Sample Input
2 2 3
Sample Output
1 2 2 1 3
Explanation
In the first case there are two possible permutations [1,2] and [2,1]. Both of the given permutations satisfy the given constraints and [1,2] is lexicographically smaller than [2,1]. In the second case, the two possible permutations are [2,1,3] and [3,1,2], of which the former is lexicographically smaller.
Is there a more efficient way to go about doing this?
from itertools import permutations
def check_condition(perm,checksum):
for i in range(len(perm)-1):
if perm[i] + perm[i+1] <= checksum:
continue
else:
return False
return True
testcases = int(raw_input())
current = 1
while current <= testcases:
max_ = int(raw_input())
checksum = max_ + 1
list_ = range(1,max_+1)
for perm in permutations(list_):
#print(perm)
if check_condition(perm,checksum):
print(" ".join(map(str,perm)))
break
current += 1