← 返回题目列表

Codeforces · 794/C

C. 命名公司

中文机器翻译题面 查看原题

客户 Oleg 和分析师 Igor 是好朋友。不过,有时他们也会因为一些小事而争吵。最近,他们创办了一家新公司,但在为公司取名时遇到了困难。

为了解决这个问题,他们决定玩一个游戏。公司名称由n个字母组成。 Oleg 和 Igor 各有一组 n 个字母(可能包含同一字母的多个副本,这些字母组可以不同)。最初,公司名称由n个问号表示。奥列格和伊戈尔轮流玩游戏,奥列格先行动。在每一回合中,玩家可以选择他的集合中的字母 c 之一,并用 c 替换任何问号。然后,字母 c 的副本从他的集合中删除。当所有问号都被某个字母取代时,游戏结束。

例如,假设 Oleg 有一组字母 {i, o, i},而 Igor 有一组字母 {i, m, o}。一种可能的游戏如下:

最初,公司名称是???。

Oleg 将第二个问号替换为“i”。公司名称变为“i”。 Oleg 现在拥有的字母集是 {i, o}。

Igor 将第三个问号替换为“o”。公司名称变为?io。 Igor 现在拥有的字母集是 {i, m}。

最后,Oleg 将第一个问号替换为“o”。公司名称变为oio。 Oleg 现在拥有的字母集是 {i}。

最后,公司名称为oio。

Oleg 希望公司名称按字典顺序尽可能小,而 Igor 希望公司名称按字典顺序尽可能大。如果奥列格和伊戈尔总是发挥最佳状态,公司的名称是什么?

如果 si < ti,其中 i 是满足 si ≠ ti 的最小索引,则按字典顺序,字符串 s = s1s2...sm 被称为小于字符串 t = t1t2...tm(其中 s ≠ t)。 (所以 sj = tj 对于所有 j < i)

输入

输入的第一行包含长度为 n (1 ≤ n ≤ 3·105) 的字符串 s。字符串中的所有字符都是小写英文字母。该字符串表示 Oleg 最初的字母集。

输入的第二行包含长度为 n 的字符串 t。字符串中的所有字符都是小写英文字母。该字符串表示 Igor 最初拥有的字母集。

输出

输出应包含一个由 n 个小写英文字母组成的字符串,表示 Oleg 和 Igor 发挥最佳状态时的公司名称。

示例

输入 #1

tinkoff
zscoder

输出 #1

fzfsirk

输入 #2

xxxxxx
xxxxxx

输出 #2

xxxxxx

输入 #3

ioi
imo

输出 #3

ioi

注意

在第一个示例中实现最佳播放效果的一种方法如下:

- 最初,公司名称是??????。
- Oleg 将第一个问号替换为“f”。公司名称变成f??????。
- Igor 将第二个问号替换为“z”。公司名称变成fz??????。
- Oleg 将第三个问号替换为“f”。公司名称变成fzf???。
- Igor 将第四个问号替换为“s”。公司名称变成fzfs???。
- Oleg 将第五个问号替换为“i”。公司名称变成fzfsi??。
- Igor 将第六个问号替换为“r”。公司名称变为fzfsir?。
- Oleg 将第七个问号替换为“k”。公司名称变为 fzfsirk。

对于第二个样本,无论他们如何发挥,公司名称始终是xxxxxx。