/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
N 人の人があるコンテストに参加し、i 位の人のハンドルネームは S_i でした。
上位 K 人のハンドルネームを辞書順に出力してください。
辞書順とは？
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。
以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
制約
- 1 \leq K \leq N \leq 100
- K, N は整数
- S_i は英小文字からなる長さ 10 以下の文字列
- i \neq j ならば S_i \neq S_j
入力
入力は以下の形式で標準入力から与えられる。
N K S_1 S_2 \vdots S_N
出力
答えを改行区切りで出力せよ。
入力例 1
5 3 abc aaaaa xyz a def
出力例 1
aaaaa abc xyz
このコンテストには 5 人が参加し、1 位の人のハンドルネームは abc 、2 位の人のハンドルネームは aaaaa 、3 位の人のハンドルネームは xyz 、4 位の人のハンドルネームは a 、5 位の人のハンドルネームは def でした。
上位 3 人のハンドルネームは abc、aaaaa、xyz であるため、これを辞書順に並べ替えて aaaaa 、abc 、xyz の順に出力します。
入力例 2
4 4 z zyx zzz rbg
出力例 2
rbg z zyx zzz
入力例 3
3 1 abc arc agc
出力例 3
abc
Score : 200 points
Problem Statement
There were N participants in a contest. The participant ranked i-th had the nickname S_i.
Print the nicknames of the top K participants in lexicographical order.
What is lexicographical order?
Simply put, the lexicographical order is the order of words in a dictionary. As a formal description, below is an algorithm to order distinct strings S and T.
Let S_i denote the i-th character of a string S. We write S \lt T if S is lexicographically smaller than T, and S \gt T if S is larger.
- Let L be the length of the shorter of S and T. For i=1,2,\dots,L, check whether S_i equals T_i.
- If there is an i such that S_i \neq T_i, let j be the smallest such i. Compare S_j and T_j. If S_j is alphabetically smaller than T_j, we get S \lt T; if S_j is larger, we get S \gt T.
- If there is no i such that S_i \neq T_i, compare the lengths of S and T. If S is shorter than T, we get S \lt T; if S is longer, we get S \gt T.
Constraints
- 1 \leq K \leq N \leq 100
- K and N are integers.
- S_i is a string of length 10 consisting of lowercase English letters.
- S_i \neq S_j if i \neq j.
Input
The input is given from Standard Input in the following format:
N K S_1 S_2 \vdots S_N
Output
Print the nicknames, separated by newlines.
Sample Input 1
5 3 abc aaaaa xyz a def
Sample Output 1
aaaaa abc xyz
This contest had five participants. The participants ranked first, second, third, fourth, and fifth had the nicknames abc, aaaaa, xyz, a, and def, respectively.
The nicknames of the top three participants were abc, aaaaa, xyz, so print these in lexicographical order: aaaaa, abc, xyz.
Sample Input 2
4 4 z zyx zzz rbg
Sample Output 2
rbg z zyx zzz
Sample Input 3
3 1 abc arc agc
Sample Output 3
abc