G. Name the album

Codeforces

IDCF100G

Time2000ms

Memory64MB

Difficulty—

data structuresimplementation

English · Original

Chinese · Translation

Formal · Original

The famous singer, Aryo, is going to publish a new album of his great work! Unfortunately these days, there are many albums, Aryo wants to choose a new name for his album, a name that has not been used or at least has not been used recently. He has a list of all used album names together with the year the albums were published. He also has a list of suitable names for his album. If he finds a suitable name which has not been used before, he'll use it. Otherwise he will use the name which was used as long ago as possible. If two such names are found (that haven't been used or were used at the same year), he uses the name that is alphabetically latest. Help him name his album. ## Input The first line contains a single integer _n_ (0 ≤ _n_ ≤ 105), the number of used names. The following _n_ lines each contain a string (the album name) and an integer (the year album was published). Album names are made of lowercase Latin letters and contain at most 14 letters. The year is in range \[1900, 2011\]. The following line contains a single integer _m_ (1 ≤ _m_ ≤ 104), the number of suitable album names. The following _m_ lines each contain a string — a suitable name. It contains at most 14 lowercase Latin letters. All album names and suitable names are non-empty. ## Output Write a single string. The name of the new album. [samples]

著名歌手 Aryo 即将发布他的新专辑！然而，如今专辑数量众多，Aryo 希望为他的专辑选择一个未曾使用过、或至少近期未曾使用过的名称。他拥有一份所有已使用专辑名称及其发布年份的列表，同时也有一份适合他专辑的候选名称列表。如果他找到一个从未使用过的候选名称，他将直接使用它。否则，他会选择使用时间最久远的名称。如果存在多个这样的名称（即从未使用过，或均在同一年使用过），他将选择字母序最靠后的名称。请帮助他为专辑命名。第一行包含一个整数 #cf_span[n]（#cf_span[0 ≤ n ≤ 10^5]），表示已使用名称的数量。接下来的 #cf_span[n] 行，每行包含一个字符串（专辑名称）和一个整数（专辑发布的年份）。专辑名称由小写拉丁字母组成，长度不超过 #cf_span[14] 个字符。年份范围为 #cf_span[[1900, 2011]]。接下来一行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 10^4]），表示候选名称的数量。接下来的 #cf_span[m] 行，每行包含一个字符串——一个候选名称。它由至多 #cf_span[14] 个小写拉丁字母组成。所有专辑名称和候选名称均为 #cf_span(class=[tex-font-style-underline], body=[non-empty])。请输出一个字符串，即新专辑的名称。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[0 ≤ n ≤ 10^5]），表示已使用名称的数量。接下来的 #cf_span[n] 行，每行包含一个字符串（专辑名称）和一个整数（专辑发布的年份）。专辑名称由小写拉丁字母组成，长度不超过 #cf_span[14] 个字符。年份范围为 #cf_span[[1900, 2011]]。接下来一行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 10^4]），表示候选名称的数量。接下来的 #cf_span[m] 行，每行包含一个字符串——一个候选名称。它由至多 #cf_span[14] 个小写拉丁字母组成。所有专辑名称和候选名称均为 #cf_span(class=[tex-font-style-underline], body=[non-empty])。 ## Output 请输出一个字符串，即新专辑的名称。 [samples]

**Definitions** Let $ U = \{(s_i, y_i) \mid i \in \{1, \dots, n\} \} $ be the set of used album names, where $ s_i \in \Sigma^{*} $ is a non-empty string of lowercase Latin letters (length $ \leq 14 $) and $ y_i \in \mathbb{Z} \cap [1900, 2011] $ is the publication year. Let $ S = \{t_j \mid j \in \{1, \dots, m\} \} $ be the set of suitable names, where $ t_j \in \Sigma^{*} $ is a non-empty string of lowercase Latin letters (length $ \leq 14 $). **Constraints** 1. $ 0 \leq n \leq 10^5 $ 2. $ 1 \leq m \leq 10^4 $ 3. All strings consist only of lowercase Latin letters and are non-empty. 4. Years satisfy $ 1900 \leq y_i \leq 2011 $. **Objective** Find the album name $ t^* \in S $ such that: - If $ \exists t_j \in S $ with $ t_j \notin \{ s_i \mid (s_i, y_i) \in U \} $, then choose the lexicographically latest such $ t_j $. - Otherwise, choose $ t_j \in S $ that maximizes $ \min_{(s_i, y_i) \in U} \{ y_i \mid s_i = t_j \} $ (i.e., the earliest year among used names matching $ t_j $), and if tied, choose the lexicographically latest $ t_j $. Formally: Let $ V = \{ t_j \in S \mid t_j \notin \{ s_i \mid (s_i, y_i) \in U \} \} $. If $ V \neq \emptyset $, then: $$ t^* = \arg\max_{t \in V} t \quad \text{(lexicographically)} $$ Else: Let $ W = \{ t_j \in S \mid \exists (s_i, y_i) \in U \text{ s.t. } s_i = t_j \} $, and define $ f(t_j) = \min \{ y_i \mid (s_i, y_i) \in U \land s_i = t_j \} $. Then: $$ t^* = \arg\max_{t_j \in W} \left( f(t_j), t_j \right) \quad \text{(lexicographic order on } (f(t_j), t_j) \text{)} $$

Samples

Input #1

3
eyesonme 2008
anewdayhascome 2002
oneheart 2003
2
oneheart
bienbien

Output #1

bienbien

Input #2

2
nasimevasl 2003
basetareha 2006
2
nasimevasl
basetareha

Output #2

nasimevasl

API Response (JSON)

{
  "problem": {
    "name": "G. Name the album",
    "description": {
      "content": "The famous singer, Aryo, is going to publish a new album of his great work! Unfortunately these days, there are many albums, Aryo wants to choose a new name for his album, a name that has not been us",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF100G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The famous singer, Aryo, is going to publish a new album of his great work!\n\nUnfortunately these days, there are many albums, Aryo wants to choose a new name for his album, a name that has not been us...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "著名歌手 Aryo 即将发布他的新专辑！\n\n然而，如今专辑数量众多，Aryo 希望为他的专辑选择一个未曾使用过、或至少近期未曾使用过的名称。\n\n他拥有一份所有已使用专辑名称及其发布年份的列表，同时也有一份适合他专辑的候选名称列表。\n\n如果他找到一个从未使用过的候选名称，他将直接使用它。否则，他会选择使用时间最久远的名称。如果存在多个这样的名称（即从未使用过，或均在同一年使用过），他将选择字母序最靠...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ U = \\{(s_i, y_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of used album names, where $ s_i \\in \\Sigma^{*} $ is a non-empty string of lowercase Latin letters (length $ \\leq 14...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments