만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

베라와 평균 정렬

시간 제한2초메모리 제한256 MB

요약
길이 K인 모든 연속 구간의 조화평균이 감소하지 않으면서 다른 어떤 구간 길이 L에 대해서도 그런 성질을 만족하지 않는, 1부터 N까지의 순열 중 사전순으로 가장 작은 것을 찾는다.
난이도

보통10점 중 7점

유형
조합론, 수학, 그리디, 정렬
정답자
아직 제출이 없습니다

문제

양의 정수로 이루어진 수열 x1,x2,…,xNx_1, x_2, \dots, x_N의 조화평균을 다음과 같이 정의한다.

H(x1,…,xN)=(∑i=1Nxi−1N)−1H(x_1, \dots, x_N) = \left( \frac{\sum_{i=1}^{N} x_i^{-1}}{N} \right)^{-1}

길이가 NN인 양의 정수 배열 A=[A1,…,AN]A = [A_1, \dots, A_N]에 대해

M(i)=H(Ai,Ai+1,…,Ai+K−1)M(i) = H(A_i, A_{i+1}, \dots, A_{i+K-1})

이라고 하자. 1≤i≤N−K1 \le i \le N - K인 모든 ii에서 M(i)≥M(i+1)M(i) \ge M(i+1)이 성립하면 베라는 AA를 KK-평균정렬 배열이라고 부른다.

순열 PP는 NN 이하의 서로 다른 양의 정수 P1,P2,…,PNP_1, P_2, \dots, P_N을 순서대로 나열한 것이다.

순열 PP가 순열 QQ보다 사전순으로 작다는 것은, Pi<QiP_i < Q_i이고 1≤j<i1 \le j < i인 모든 jj에서 Pj=QjP_j = Q_j인 ii (1≤i≤N1 \le i \le N)가 존재한다는 뜻이다.

정수 NN과 KK가 주어진다. 11부터 NN까지의 정수로 이루어진 순열 PP 중에서 KK-평균정렬이면서 L≠KL \ne K인 모든 LL (1≤L≤N−11 \le L \le N - 1)에 대해 LL-평균정렬이 아닌 것을 찾아야 한다. 그런 순열이 여럿이면 사전순으로 가장 작은 것을 구해 베라를 도와라. 조건을 만족하는 순열이 없으면 00을 출력한다.

입력

입력은 다음 형식으로 주어진다.

N K

제약 조건은 다음과 같다.

  • 2≤N≤1002 \le N \le 100
  • 1≤K≤N−11 \le K \le N - 1
  • NN과 KK는 정수이다.

출력

구한 순열을 한 줄에 공백으로 구분해 출력한다. 그런 순열이 없으면 한 줄에 00을 출력한다.

예제2

  1. 예제 1

    입력
    3 2
    
    예상 출력
    2 3 1
    
  2. 예제 2

    입력
    4 1
    
    예상 출력
    0