B. Valued Keys

Codeforces

IDCF801B

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsgreedystrings

English · Original

Chinese · Translation

Formal · Original

You found a mysterious function _f_. The function takes two strings _s_1 and _s_2. These strings must consist only of lowercase English letters, and must be the same length. The output of the function _f_ is another string of the same length. The _i_\-th character of the output is equal to the minimum of the _i_\-th character of _s_1 and the _i_\-th character of _s_2. For example, _f_("_ab_", "_ba_") = "_aa_", and _f_("_nzwzl_", "_zizez_") = "_niwel_". You found two strings _x_ and _y_ of the same length and consisting of only lowercase English letters. Find any string _z_ such that _f_(_x_, _z_) = _y_, or print _\-1_ if no such string _z_ exists. ## Input The first line of input contains the string _x_. The second line of input contains the string _y_. Both _x_ and _y_ consist only of lowercase English letters, _x_ and _y_ have same length and this length is between 1 and 100. ## Output If there is no string _z_ such that _f_(_x_, _z_) = _y_, print _\-1_. Otherwise, print a string _z_ such that _f_(_x_, _z_) = _y_. If there are multiple possible answers, print any of them. The string _z_ should be the same length as _x_ and _y_ and consist only of lowercase English letters. [samples] ## Note The first case is from the statement. Another solution for the second case is "_zizez_" There is no solution for the third case. That is, there is no _z_ such that _f_("_ab_", _z_) = "_ba_".

你发现了一个神秘的函数 #cf_span[f]。该函数接受两个字符串 #cf_span[s1] 和 #cf_span[s2]。这些字符串必须仅由小写英文字母组成，且长度必须相同。函数 #cf_span[f] 的输出是另一个相同长度的字符串。输出的第 #cf_span[i] 个字符等于 #cf_span[s1] 的第 #cf_span[i] 个字符与 #cf_span[s2] 的第 #cf_span[i] 个字符中的最小值。例如，#cf_span[f(]"_ab_", "_ba_"#cf_span[)] = "_aa_"，且 #cf_span[f(]"_nzwzl_", "_zizez_"#cf_span[)] = "_niwel_"。你找到了两个长度相同且仅由小写英文字母组成的字符串 #cf_span[x] 和 #cf_span[y]。请找出任意一个字符串 #cf_span[z]，使得 #cf_span[f(x, z) = y]；如果不存在这样的字符串 #cf_span[z]，则输出 _-1_。输入的第一行包含字符串 #cf_span[x]。输入的第二行包含字符串 #cf_span[y]。 #cf_span[x] 和 #cf_span[y] 均仅由小写英文字母组成，且长度相同，长度介于 #cf_span[1] 和 #cf_span[100] 之间。如果不存在满足 #cf_span[f(x, z) = y] 的字符串 #cf_span[z]，请输出 _-1_。否则，请输出一个满足 #cf_span[f(x, z) = y] 的字符串 #cf_span[z]。如果有多个可能的答案，请输出任意一个。字符串 #cf_span[z] 应与 #cf_span[x] 和 #cf_span[y] 长度相同，且仅由小写英文字母组成。第一个样例来自题面。第二个样例的另一个解是 "_zizez_"。第三个样例无解。即，不存在 #cf_span[z] 使得 #cf_span[f(]"_ab_", #cf_span[z) = ] "_ba_"。 ## Input 输入的第一行包含字符串 #cf_span[x]。输入的第二行包含字符串 #cf_span[y]。#cf_span[x] 和 #cf_span[y] 均仅由小写英文字母组成，且长度相同，长度介于 #cf_span[1] 和 #cf_span[100] 之间。 ## Output 如果不存在满足 #cf_span[f(x, z) = y] 的字符串 #cf_span[z]，请输出 _-1_。否则，请输出一个满足 #cf_span[f(x, z) = y] 的字符串 #cf_span[z]。如果有多个可能的答案，请输出任意一个。字符串 #cf_span[z] 应与 #cf_span[x] 和 #cf_span[y] 长度相同，且仅由小写英文字母组成。 [samples] ## Note 第一个样例来自题面。第二个样例的另一个解是 "_zizez_"。第三个样例无解。即，不存在 #cf_span[z] 使得 #cf_span[f(]"_ab_", #cf_span[z) = ] "_ba_"。

**Definitions** Let $ x, y \in \Sigma^n $ be strings of length $ n $, where $ \Sigma = \{a, b, \dots, z\} $ is the set of lowercase English letters. Define the function $ f: \Sigma^n \times \Sigma^n \to \Sigma^n $ such that for all $ i \in \{1, \dots, n\} $: $$ f(x, z)_i = \min(x_i, z_i) $$ where $ \min $ is the lexicographic minimum (i.e., character with smaller ASCII value). **Constraints** 1. $ 1 \le n \le 100 $ 2. $ x_i, y_i \in \Sigma $ for all $ i \in \{1, \dots, n\} $ **Objective** Find a string $ z \in \Sigma^n $ such that for all $ i \in \{1, \dots, n\} $: $$ \min(x_i, z_i) = y_i $$ If no such $ z $ exists, output $-1$.

Samples

Input #1

ab
aa

Output #1

ba

Input #2

nzwzl
niwel

Output #2

xiyez

Input #3

ab
ba

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "B. Valued Keys",
    "description": {
      "content": "You found a mysterious function _f_. The function takes two strings _s_1 and _s_2. These strings must consist only of lowercase English letters, and must be the same length. The output of the functio",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF801B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You found a mysterious function _f_. The function takes two strings _s_1 and _s_2. These strings must consist only of lowercase English letters, and must be the same length.\n\nThe output of the functio...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你发现了一个神秘的函数 #cf_span[f]。该函数接受两个字符串 #cf_span[s1] 和 #cf_span[s2]。这些字符串必须仅由小写英文字母组成，且长度必须相同。\n\n函数 #cf_span[f] 的输出是另一个相同长度的字符串。输出的第 #cf_span[i] 个字符等于 #cf_span[s1] 的第 #cf_span[i] 个字符与 #cf_span[s2] 的第 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ x, y \\in \\Sigma^n $ be strings of length $ n $, where $ \\Sigma = \\{a, b, \\dots, z\\} $ is the set of lowercase English letters.  \nDefine the function $ f: \\Sigma^n \\times \\Sigma...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments