Score : $200$ points

问题描述

在一次竞赛中有 $N$ 名参与者。排名第 $i$ 位的参赛者昵称为 $S_i$。
请按 字典序顺序 打印前 $K$ 名参赛者的昵称。

什么是字典序顺序？

简而言之，字典序顺序就是词典中单词排列的顺序。作为正式描述，以下是一种对不重复字符串 $S$ 和 $T$ 进行排序的算法。

令 $S_i$ 表示字符串 $S$ 的第 $i$ 个字符。若 $S$ 在字典序上小于 $T$，我们写为 $S \lt T$；若 $S$ 更大，则写为 $S \gt T$。

1. 计算 $S$ 和 $T$ 中较短者的长度，记为 $L$。对于 $i=1,2,\dots,L$，检查 $S_i$ 是否等于 $T_i$。
2. 若存在某个 $i$ 使得 $S_i \neq T_i$，取最小这样的 $i$ 值，记为 $j$。比较 $S_j$ 和 $T_j$。若 $S_j$ 字母表顺序上小于 $T_j$，则有 $S \lt T$；若 $S_j$ 更大，则有 $S \gt T$。
3. 若不存在使 $S_i \neq T_i$ 的 $i$，则比较 $S$ 和 $T$ 的长度。若 $S$ 比 $T$ 短，则有 $S \lt T$；若 $S$ 更长，则有 $S \gt T$。

综上所述，请按照上述字典序顺序规则，输出前 $K$ 名参赛者的昵称。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

1. 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$.
2. 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$.
3. 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

update @ 2024/3/10 12:01:36