C. Naming Company

Codeforces

IDCF794C

Time2000ms

Memory256MB

Difficulty—

gamesgreedysortings

English · Original

Chinese · Translation

Formal · Original

Oleg the client and Igor the analyst are good friends. However, sometimes they argue over little things. Recently, they started a new company, but they are having trouble finding a name for the company. To settle this problem, they've decided to play a game. The company name will consist of _n_ letters. Oleg and Igor each have a set of _n_ letters (which might contain multiple copies of the same letter, the sets can be different). Initially, the company name is denoted by _n_ question marks. Oleg and Igor takes turns to play the game, Oleg moves first. In each turn, a player can choose one of the letters _c_ in his set and replace any of the question marks with _c_. Then, a copy of the letter _c_ is removed from his set. The game ends when all the question marks has been replaced by some letter. For example, suppose Oleg has the set of letters {_i_, _o_, _i_} and Igor has the set of letters {_i_, _m_, _o_}. One possible game is as follows : Initially, the company name is _???_. Oleg replaces the second question mark with _'i'_. The company name becomes _?i?_. The set of letters Oleg have now is {_i_, _o_}. Igor replaces the third question mark with _'o'_. The company name becomes _?io_. The set of letters Igor have now is {_i_, _m_}. Finally, Oleg replaces the first question mark with _'o'_. The company name becomes _oio_. The set of letters Oleg have now is {_i_}. In the end, the company name is _oio_. Oleg wants the company name to be as lexicographically small as possible while Igor wants the company name to be as lexicographically large as possible. What will be the company name if Oleg and Igor always play optimally? A string _s_ = _s_1_s_2..._s__m_ is called lexicographically smaller than a string _t_ = _t_1_t_2..._t__m_ (where _s_ ≠ _t_) if _s__i_ < _t__i_ where _i_ is the smallest index such that _s__i_ ≠ _t__i_. (so _s__j_ = _t__j_ for all _j_ < _i_) ## Input The first line of input contains a string _s_ of length _n_ (1 ≤ _n_ ≤ 3·105). All characters of the string are lowercase English letters. This string denotes the set of letters Oleg has initially. The second line of input contains a string _t_ of length _n_. All characters of the string are lowercase English letters. This string denotes the set of letters Igor has initially. ## Output The output should contain a string of _n_ lowercase English letters, denoting the company name if Oleg and Igor plays optimally. [samples] ## Note One way to play optimally in the first sample is as follows : * Initially, the company name is _???????_. * Oleg replaces the first question mark with _'f'_. The company name becomes _f??????_. * Igor replaces the second question mark with _'z'_. The company name becomes _fz?????_. * Oleg replaces the third question mark with _'f'_. The company name becomes _fzf????_. * Igor replaces the fourth question mark with _'s'_. The company name becomes _fzfs???_. * Oleg replaces the fifth question mark with _'i'_. The company name becomes _fzfsi??_. * Igor replaces the sixth question mark with _'r'_. The company name becomes _fzfsir?_. * Oleg replaces the seventh question mark with _'k'_. The company name becomes _fzfsirk_. For the second sample, no matter how they play, the company name will always be _xxxxxx_.

Oleg 客户和 Igor 分析师是好朋友。然而，他们有时会为一些小事争论。最近，他们创办了一家新公司，但在公司名称上遇到了困难。为了解决这个问题，他们决定玩一个游戏。公司名称将由 #cf_span[n] 个字母组成。Oleg 和 Igor 各自拥有一组 #cf_span[n] 个字母（可能包含重复字母，两组字母可能不同）。初始时，公司名称用 #cf_span[n] 个问号表示。Oleg 和 Igor 轮流进行游戏，Oleg 先手。每轮，一名玩家可以从自己的字母集合中选择一个字母 #cf_span[c]，并用 #cf_span[c] 替换任意一个问号。然后，该字母 #cf_span[c] 的一个副本将从他的集合中移除。当所有问号都被字母替换时，游戏结束。例如，假设 Oleg 的字母集合为 #cf_span[{i, o, i}]，Igor 的字母集合为 #cf_span[{i, m, o}]。一场可能的游戏如下：初始时，公司名称为 _???_。 Oleg 将第二个问号替换为 _'i'_。公司名称变为 _?i?_。此时 Oleg 的字母集合为 #cf_span[{i, o}]。 Igor 将第三个问号替换为 _'o'_。公司名称变为 _?io_。此时 Igor 的字母集合为 #cf_span[{i, m}]。最后，Oleg 将第一个问号替换为 _'o'_。公司名称变为 _oio_。此时 Oleg 的字母集合为 #cf_span[{i}]。最终，公司名称为 _oio_。 Oleg 希望公司名称的字典序尽可能小，而 Igor 希望公司名称的字典序尽可能大。如果 Oleg 和 Igor 都采取最优策略，公司名称会是什么？字符串 #cf_span[s = s1s2...sm] 被称为字典序小于字符串 #cf_span[t = t1t2...tm]（其中 #cf_span[s ≠ t]），如果存在最小的下标 #cf_span[i] 使得 #cf_span[si < ti]（即对所有 #cf_span[j < i]，有 #cf_span[sj = tj]）。输入的第一行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]（#cf_span[1 ≤ n ≤ 3·105]）。该字符串的所有字符均为小写英文字母，表示 Oleg 初始拥有的字母集合。输入的第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[t]（#cf_span[1 ≤ n ≤ 3·105]）。该字符串的所有字符均为小写英文字母，表示 Igor 初始拥有的字母集合。输出应为一个长度为 #cf_span[n] 的小写英文字母字符串，表示在 Oleg 和 Igor 均采取最优策略时的公司名称。第一个样例的一种最优玩法如下：对于第二个样例，无论他们如何玩，公司名称始终为 _xxxxxx_。 ## Input 输入的第一行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]（#cf_span[1 ≤ n ≤ 3·105]）。该字符串的所有字符均为小写英文字母，表示 Oleg 初始拥有的字母集合。输入的第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[t]（#cf_span[1 ≤ n ≤ 3·105]）。该字符串的所有字符均为小写英文字母，表示 Igor 初始拥有的字母集合。 ## Output 输出应为一个长度为 #cf_span[n] 的小写英文字母字符串，表示在 Oleg 和 Igor 均采取最优策略时的公司名称。 [samples] ## Note 第一个样例的一种最优玩法如下：初始时，公司名称为 _???????_。Oleg 将第一个问号替换为 _'f'_。公司名称变为 _f??????_。Igor 将第二个问号替换为 _'z'_。公司名称变为 _fz?????_。Oleg 将第三个问号替换为 _'f'_。公司名称变为 _fzf????_。Igor 将第四个问号替换为 _'s'_。公司名称变为 _fzfs???_。Oleg 将第五个问号替换为 _'i'_。公司名称变为 _fzfsi??_。Igor 将第六个问号替换为 _'r'_。公司名称变为 _fzfsir?_。Oleg 将第七个问号替换为 _'k'_。公司名称变为 _fzfsirk_。对于第二个样例，无论他们如何玩，公司名称始终为 _xxxxxx_。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the company name. Let $ O \subseteq \Sigma $ be the multiset of letters Oleg initially has, represented as a string $ s $ of length $ n $. Let $ I \subseteq \Sigma $ be the multiset of letters Igor initially has, represented as a string $ t $ of length $ n $. Let $ \Sigma = \{a, b, \dots, z\} $ be the alphabet of lowercase English letters. **Constraints** 1. $ 1 \leq n \leq 3 \cdot 10^5 $ 2. $ |O| = |I| = n $ 3. All characters in $ O $ and $ I $ are from $ \Sigma $. **Objective** The players alternate turns, with Oleg moving first. On each turn, a player selects one letter from their multiset and places it in any remaining position of the $ n $-length string (initially all '?'). The letter is then removed from their multiset. - Oleg aims to **minimize** the lexicographic value of the final string. - Igor aims to **maximize** the lexicographic value of the final string. Both play optimally. Compute the resulting string after $ n $ moves.

Samples

Input #1

tinkoff
zscoder

Output #1

fzfsirk

Input #2

xxxxxx
xxxxxx

Output #2

xxxxxx

Input #3

ioi
imo

Output #3

ioi

API Response (JSON)

{
  "problem": {
    "name": "C. Naming Company",
    "description": {
      "content": "Oleg the client and Igor the analyst are good friends. However, sometimes they argue over little things. Recently, they started a new company, but they are having trouble finding a name for the compan",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF794C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Oleg the client and Igor the analyst are good friends. However, sometimes they argue over little things. Recently, they started a new company, but they are having trouble finding a name for the compan...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Oleg 客户和 Igor 分析师是好朋友。然而，他们有时会为一些小事争论。最近，他们创办了一家新公司，但在公司名称上遇到了困难。\n\n为了解决这个问题，他们决定玩一个游戏。公司名称将由 #cf_span[n] 个字母组成。Oleg 和 Igor 各自拥有一组 #cf_span[n] 个字母（可能包含重复字母，两组字母可能不同）。初始时，公司名称用 #cf_span[n] 个问号表示。Oleg 和 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the company name.  \nLet $ O \\subseteq \\Sigma $ be the multiset of letters Oleg initially has, represented as a string $ s $ of length $ n ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments