A. Generate Login

Codeforces

IDCF909A

Time2000ms

Memory256MB

Difficulty—

brute forcegreedysortings

English · Original

Chinese · Translation

Formal · Original

The preferred way to generate user login in Polygon is to concatenate a prefix of the user's first name and a prefix of their last name, in that order. Each prefix must be non-empty, and any of the prefixes can be the full name. Typically there are multiple possible logins for each person. You are given the first and the last name of a user. Return the alphabetically earliest login they can get (regardless of other potential Polygon users). As a reminder, a prefix of a string _s_ is its substring which occurs at the beginning of _s_: "_a_", "_ab_", "_abc_" etc. are prefixes of string "{abcdef}" but "_b_" and '_bc_" are not. A string _a_ is alphabetically earlier than a string _b_, if _a_ is a prefix of _b_, or _a_ and _b_ coincide up to some position, and then _a_ has a letter that is alphabetically earlier than the corresponding letter in _b_: "_a_" and "_ab_" are alphabetically earlier than "_ac_" but "_b_" and "_ba_" are alphabetically later than "_ac_". ## Input The input consists of a single line containing two space-separated strings: the first and the last names. Each character of each string is a lowercase English letter. The length of each string is between 1 and 10, inclusive. ## Output Output a single string — alphabetically earliest possible login formed from these names. The output should be given in lowercase as well. [samples]

在 Polygon 中生成用户登录名的首选方法是将用户的名的前缀和姓的前缀按此顺序拼接。每个前缀必须非空，且任一前缀都可以是完整的名字。通常，每个人都有多个可能的登录名。给你一个用户的名和姓，请返回他们能得到的字典序最小的登录名（不考虑其他可能的 Polygon 用户）。作为提醒，字符串 #cf_span[s] 的前缀是出现在 #cf_span[s] 开头的子串："_a_"、"_ab_"、"_abc_" 等是字符串 "{abcdef}" 的前缀，但 "_b_" 和 '_bc_" 不是。字符串 #cf_span[a] 字典序早于字符串 #cf_span[b]，当且仅当 #cf_span[a] 是 #cf_span[b] 的前缀，或者 #cf_span[a] 和 #cf_span[b] 在某个位置之前完全相同，而在此位置之后 #cf_span[a] 的字母在字典序上早于 #cf_span[b] 中对应位置的字母："_a_" 和 "_ab_" 字典序早于 "_ac_"，但 "_b_" 和 "_ba_" 字典序晚于 "_ac_"。输入由一行组成，包含两个用空格分隔的字符串：名和姓。每个字符串中的每个字符均为小写英文字母。每个字符串的长度在 1 到 10 之间（含端点）。输出一个字符串 —— 由这两个名字构成的字典序最小的可能登录名。输出也应为小写字母。 ## Input 输入由一行组成，包含两个用空格分隔的字符串：名和姓。每个字符串中的每个字符均为小写英文字母。每个字符串的长度在 1 到 10 之间（含端点）。 ## Output 输出一个字符串 —— 由这两个名字构成的字典序最小的可能登录名。输出也应为小写字母。 [samples]

Let $ f, l \in \Sigma^* $ be the first and last names, respectively, where $ \Sigma = \{a, b, \dots, z\} $, $ |f| \geq 1 $, $ |l| \geq 1 $, and $ |f|, |l| \leq 10 $. Let $ P_f = \{ f[1:i] \mid i \in \{1, \dots, |f|\} \} $ be the set of non-empty prefixes of $ f $, and $ P_l = \{ l[1:j] \mid j \in \{1, \dots, |l|\} \} $ be the set of non-empty prefixes of $ l $. Define the set of possible logins: $ L = \{ p_f + p_l \mid p_f \in P_f, p_l \in P_l \} $, where $ + $ denotes string concatenation. Objective: Find $ \min_{\text{lex}} L $, the lexicographically smallest string in $ L $.

Samples

Input #1

harry potter

Output #1

hap

Input #2

tom riddle

Output #2

tomr

API Response (JSON)

{
  "problem": {
    "name": "A. Generate Login",
    "description": {
      "content": "The preferred way to generate user login in Polygon is to concatenate a prefix of the user's first name and a prefix of their last name, in that order. Each prefix must be non-empty, and any of the pr",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF909A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The preferred way to generate user login in Polygon is to concatenate a prefix of the user's first name and a prefix of their last name, in that order. Each prefix must be non-empty, and any of the pr...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在 Polygon 中生成用户登录名的首选方法是将用户的名的前缀和姓的前缀按此顺序拼接。每个前缀必须非空，且任一前缀都可以是完整的名字。通常，每个人都有多个可能的登录名。\n\n给你一个用户的名和姓，请返回他们能得到的字典序最小的登录名（不考虑其他可能的 Polygon 用户）。\n\n作为提醒，字符串 #cf_span[s] 的前缀是出现在 #cf_span[s] 开头的子串：\"_a_\"、\"_ab_\"、...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ f, l \\in \\Sigma^* $ be the first and last names, respectively, where $ \\Sigma = \\{a, b, \\dots, z\\} $, $ |f| \\geq 1 $, $ |l| \\geq 1 $, and $ |f|, |l| \\leq 10 $.\n\nLet $ P_f = \\{ f[1:i] \\mid i \\in ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments