PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS HACKS ROOM STANDINGS CUSTOM INVOCATION
H. Keygen 3
time limit per test: 4 seconds
memory limit per test: 256 megabytes
Trey Frey - Refresh
⠀
A permutation∗ of length n is called valid if it has both of the following properties:
It is bitonic† ;
Exactly m of its subsets are cycles‡ .
Let k denote the number of permutations satisfying the above condition. Your task is to
find and print min(k, 2000) examples of such permutations.
†
A permutation p1 , p2 , … , pn is bitonic if there exists an index i (1 ≤ i ≤ n ) such
that
pj−1 ≤ pj for 2 ≤ j ≤ i ;
pj ≥ pj+1 for i ≤ j ≤ n − 1 .
‡
A subset C ⊆ {1, 2, … , n} is a cycle if it satisfies the following conditions:
C is non-empty;
if x ∈ C , then px ∈ C ;
C is minimal, i.e., there does not exist a cycle C such that C .
′ ′
⊂ C
∗
A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order.
For example, [2, 3, 1, 5, 4] is a permutation, but [1, 2, 2] is not a permutation (2 appears twice in the
array), and [1, 3, 4] is also not a permutation (n = 3 but there is 4 in the array).
Input
The input consists of a single line containing two integers n, m (
1 ≤ m ≤ n ≤ 100 ) — the length of the permutations and the target number of
cycles.
Output
In the first line, print a single integer r : the number of permutations you are going to
print. Note that r must be min(k, 2000) as defined in the statement.
Then, print r lines. Each line must contain a bitonic permutation of length n, with m
cycles.
Example
input Copy
6 3
output Copy
9
1 4 5 6 3 2
6 5 4 3 2 1
1 2 4 5 6 3
1 2 5 6 4 3
1 3 4 6 5 2
1 5 6 4 3 2
3 5 6 4 2 1
1 3 6 5 4 2
2 6 5 4 3 1
Note
In the example, there are 9 valid permutations (i.e., bitonic permutations of length 6,
with 3 cycles). For example, [3, 5, 6, 4, 2, 1] is bitonic (in the above definition, i = 3),
and it has 3 cycles: {1, 3, 6}, {2, 5}, {4}. So you have to print
r = min(9, 2000) = 9 such permutations.