Student Shuffle
Time limit2sMemory limit128 MB
Count permutations of up to 16 students so that every pair of adjacent heights differs by more than a given value K.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Bit manipulation, Backtracking, Combinatorics
- Solved
- No attempts yet
Problem
There are N students standing in a line. Rearrange all of them into a new order, using each student exactly once. In the new order, the height difference between every pair of adjacent students must be greater than K.
For example, the order 1, 3, 5, 2, 6, 4 has every adjacent height difference greater than 1. The order 1, 3, 6, 5, 2, 4 does not satisfy the condition because 6 and 5 differ by 1.
Count the number of valid rearrangements. Even if two students have the same height, they are counted as different students.
Input
The first line contains the number of students N (1 ≤ N ≤ 16) and the value K (1 ≤ K ≤ 3,400), which every adjacent height difference must exceed.
Each of the next N lines contains one student's height in the current standing order. Every height is a positive integer no greater than 25,000.
Output
Print the number of possible arrangements that satisfy the condition.