16530: 改卷子

string, http://cs101.openjudge.cn/practice/16530/

闫老师希望将所有学生的卷子按姓名分成两摞，交给两位助教批改。假设每位考生姓名由大写字母组成。你想出来一个好办法：你给出一个字符串，然后让闫老师将每位同学姓名的每个字母依次与该字符串比较。为了使这个过程更简单，你认为这个字符串应该尽可能的短。现在有n位学生，请你找出这样一个字符串S，使得学生姓名小于或等于S的有一半，而另一半学生姓名大于S。如果有多个字符串满足最短长度，那么就取字母排序最小的那个字符串。

输入

每组数据以n开始，代表n个学生。(n >= 2 && n <= 1000 && n为偶数)。接下来n行为学生姓名。每个名字都由大写字母组成，长度小于30个字母。

输出

针对每组数据，一行输出一个符合条件的最短字符串（大写字母）。

样例输入

Sample Input1:
2
LARHONDA
LARSEN

Sample Output1:
LARI

Sample Iutput2:
4
SAM
FRED
JOE
MARGARET

Sample Output2:
K

样例输出

Sample Iutput3:
2
A
C

Sample Output3:
A

Sample Iutput4:
2
AYZZ
AZ

Sample Output4:
AYZZ

来源: cs10117 Final Exam

python

n = int(input())
words = []
for i in range(n):
    words.append(input())

words.sort()
k = n//2
mid, afterMid = words[k-1:k+1]
ok = False
rst = ""
temp = ""
cur = 0
length = len(mid)
while cur < length:
    for i in range(26):
        rst = temp
        rst += chr(i+65)
        if mid <= rst <afterMid:
            ok = True
            break
    if ok:
        break
    temp += mid[cur]
    cur += 1

print(rst)

16530: 改卷子 ​

16530: 改卷子