Codeforces Round #309(Div.2) D 아키텍처
3831 단어 자세 기교 + 구조
D. Kyoya and Permutation
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Let's define the permutation of length n as an array p = [p1, p2, ..., pn] consisting of n distinct integers from range from 1 to n. We say that this permutation maps value 1 into the value p1, value 2 into the value p2 and so on.
Kyota Ootori has just learned about cyclic representation of a permutation. A cycle is a sequence of numbers such that each element of this sequence is being mapped into the next element of this sequence (and the last element of the cycle is being mapped into the first element of the cycle). The cyclic representation is a representation of p as a collection of cycles forming p. For example, permutation p = [4, 1, 6, 2, 5, 3] has a cyclic representation that looks like (142)(36)(5) because 1 is replaced by 4, 4 is replaced by 2, 2 is replaced by 1, 3 and 6 are swapped, and 5 remains in place.
Permutation may have several cyclic representations, so Kyoya defines the standard cyclic representation of a permutation as follows. First, reorder the elements within each cycle so the largest element is first. Then, reorder all of the cycles so they are sorted by their first element. For our example above, the standard cyclic representation of [4, 1, 6, 2, 5, 3] is (421)(5)(63).
Now, Kyoya notices that if we drop the parenthesis in the standard cyclic representation, we get another permutation! For instance, [4, 1, 6, 2, 5, 3] will become [4, 2, 1, 5, 6, 3].
Kyoya notices that some permutations don't change after applying operation described above at all. He wrote all permutations of length n that do not change in a list in lexicographic order. Unfortunately, his friend Tamaki Suoh lost this list. Kyoya wishes to reproduce the list and he needs your help. Given the integers n and k, print the permutation that was k-th on Kyoya's list.
Input
The first line will contain two integers n, k (1 ≤ n ≤ 50, 1 ≤ k ≤ min{1018, l} where l is the length of the Kyoya's list).
Output
Print n space-separated integers, representing the permutation that is the answer for the question.
Examples
input
4 3
output
1 3 2 4
input
10 1
output
1 2 3 4 5 6 7 8 9 10
Note
The standard cycle representation is (1)(32)(4), which after removing parenthesis gives us the original permutation. The first permutation on the list would be [1, 2, 3, 4], while the second permutation would be [1, 2, 4, 3].
제목:
cycle, 같은 위치에 있지 않은 수로 하나의 동그라미가 된다
모든cycle은 큰 것부터 작은 것까지 정렬하고 모든cycle은 첫 번째 요소에 따라 큰 것부터 작은 것까지 정렬합니다
정렬이 끝난 후에 원래의 서열과 변하지 않는 것이 합법적이다
그리고 k번째 합법적인 그룹을 출력하라고 합니다.
사고방식: 경신을 봐라
코드:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include