Mixed up numbers
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 158
Solved: 37
- Description
- We have N (4 <= N <= 16) different positive integers S_i (1 <= S_i <=25,000), and each of them is not larger than 25,000. Now we put them in a line but we don't want to get a "Mixed up" sequence. An order is "Mixed up" if the sequence is such that every pair of consecutive numbers in line differs by more than K(1 <= K <= 3400).
For example, if N = 6 and K = 1, then "1, 3, 5, 2, 6, 4" is a "Mixed up" line, but "1, 3, 6, 5, 2, 4" is not (since the consectutive numbers 5 and 6 differ by 1).
Then, how many different ways can N numbers be "Mixed up"?
- Input
- Line 1: Two space-separated integers: N and K
Line 2..N+1: Line i+1 contains a single integer that is the ith
number: S_i
- Output
- Line 1: A single integer that is the number of ways that N numbers can be "Mined up". The answer is guaranteed to fit in a 64-bit integer.
- sample input
-
4 1 3 4 2 1
- sample output
-
2
- hint
- source
- Ai.Freedom