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.
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.
- \$1 \le T \le 5\$
- \$2 \le N \le 105\$
\$T\$ lines each containing the permutation; the numbers in each line should be seperated by a single space.
2 2 3
1 2 2 1 3
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