Problems
From the integers 1 through N, selecting K numbers forms what is called a combination.
For example, when N = 5 and K = 3, all possible combinations are:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Cases such as [1 2 3] and [3 1 2], which contain the same selected numbers but in different order, are considered the same combination.
In other words, the order of selection does not matter.
Therefore, a sequence like [3 1 2] is considered invalid in this problem.
Only sequences sorted in ascending order are regarded as valid combinations.
Given N and K, and given a combination A of length K,
write a program to determine which number (rank) the given combination A corresponds to when all valid combinations are sorted in ascending order.
Input
The first line contains N and K (5 ≤ N ≤ 10, 1 ≤ K ≤ N).
The second line contains K integers, representing the combination A.
Output
Print the rank (1-based) of the given combination A among all combinations sorted in ascending order.
If the given combination does not exist among the valid combinations, print "None".
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 50 | The given combination A is guaranteed to be valid. |
| #2 | 50 | No additional restrictions |
Example #1
5 3
1 3 5
5
Example #2
5 3
2 1 3
None
You must sign in to write code.