Problem - 1716B - Codeforces
codeforces.com
- 제목
Permutation Chain
- 조건
time limit per test : 2 second
memory limit per test : 256 megabytes
input : standard input
output : standard output
- 문제
A permutation of length n is a sequence of integers from 1 to n such that each integer appears in it exactly once.
Let the fixedness of a permutation p be the number of fixed points in it — the number of positions j such that pj=j, where pj is the j-th element of the permutation p.
You are asked to build a sequence of permutations a1,a2,…, starting from the identity permutation (permutation a1=[1,2,…,n]). Let's call it a permutation chain. Thus, ai is the i-th permutation of length n.
For every i from 2 onwards, the permutation ai should be obtained from the permutation ai−1 by swapping any two elements in it (not necessarily neighboring). The fixedness of the permutation ai should be strictly lower than the fixedness of the permutation ai−1.
Consider some chains for n=3:
a1=[1,2,3], a2=[1,3,2] — that is a valid chain of length 2. From a1 to a2, the elements on positions 2 and 3 get swapped, the fixedness decrease from 3 to 1.
a1=[2,1,3], a2=[3,1,2] — that is not a valid chain. The first permutation should always be [1,2,3] for n=3.
a1=[1,2,3], a2=[1,3,2], a3=[1,2,3] — that is not a valid chain. From a2 to a3, the elements on positions 2 and 3 get swapped but the fixedness increase from 1 to 3.
a1=[1,2,3], a2=[3,2,1], a3=[3,1,2] — that is a valid chain of length 3. From a1 to a2, the elements on positions 1 and 3 get swapped, the fixedness decrease from 3 to 1. From a2 to a3, the elements on positions 2 and 3 get swapped, the fixedness decrease from 1 to 0.
Find the longest permutation chain. If there are multiple longest answers, print any of them.
- 입력
The first line contains a single integer t (1≤t≤99) — the number of testcases.
The only line of each testcase contains a single integer n (2≤n≤100) — the required length of permutations in the chain.
- 출력
For each testcase, first, print the length of a permutation chain k.
Then print k permutations a1,a2,…,ak. a1 should be an identity permutation of length n ([1,2,…,n]). For each i from 2 to k, ai should be obtained by swapping two elements in ai−1. It should also have a strictly lower fixedness than ai−1.
| 예제 입력1 | 예제 출력1 |
| 2 2 3 |
2 1 2 2 1 3 1 2 3 3 2 1 3 1 2 |
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define endl '\n'
int arr[101];
void init(){
for(int n = 1 ; n <= 100 ; n++) arr[n] = n;
}
void show(int l){
for(int n = 1 ; n <= l ; n++){
cout << arr[n] << ' ';
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc, length;
cin >> tc;
while(tc--){
cin >> length;
init();
cout << length << endl;
show(length);
for(int n = 1 ; n < length ; n++){
int tmp = arr[n];
arr[n] = arr[n + 1];
arr[n + 1] = tmp;
show(length);
}
}
return 0;
}