Vera and Mean Sorting

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
2017 Winter Waterloo Local ACM Contest, Problem C

The harmonic mean of a sequence of positive integers x_1, \cdots, x_N is \displaystyle 
H(x_1, \cdots, x_N) = \left(\frac{\sum_{i=1}^N x_i^{-1}}{N} \right)^{-1}

Vera classifies an array of positive integers A = [A_1, \cdots, A_N] of length N as K-mean-sorted if M(i) \ge M(i+1) for 1 \le i \le N-K where \displaystyle 
M(i) = H(A_i, \cdots, A_{i+K-1})

A permutation P is an ordered set of integers P_1, P_2, \cdots, P_{N}, consisting of N distinct positive integers, each of which are at most N.

Permutation P is lexicographically smaller than permutation Q if there is i (1 \le i \le n), such that P_i < Q_i, and for any j (1 \le j < i) P_j = Q_j.

Given integers N and K, help Vera find the lexicographically smallest permutation P of integers 1 to N such that P is K-mean-sorted but not L-mean-sorted for 1 \le L \le N-1, L \ne K.

If no such permutation exists output 0.


  • 2 \le N \le 100
  • 1 \le K \le N - 1
  • N, K are integers

Input Specification

The input will be in the format:


Output Specification

Output one line with the desired permutation. If such permutation does not exist output one line with 0.

Sample Input 1

3 2

Sample Output 1

2 3 1

Sample Input 2

4 1

Sample Output 2



There are no comments at the moment.