A. Search for Pretty Integers

Codeforces

IDCF870A

Time1000ms

Memory256MB

Difficulty—

brute forceimplementation

English · Original

Chinese · Translation

Formal · Original

You are given two lists of non-zero digits. Let's call an integer pretty if its (base 10) representation has at least one digit from the first list and at least one digit from the second list. What is the smallest positive pretty integer? ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 9) — the lengths of the first and the second lists, respectively. The second line contains _n_ distinct digits _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 9) — the elements of the first list. The third line contains _m_ distinct digits _b_1, _b_2, ..., _b__m_ (1 ≤ _b__i_ ≤ 9) — the elements of the second list. ## Output Print the smallest pretty integer. [samples] ## Note In the first example 25, 46, 24567 are pretty, as well as many other integers. The smallest among them is 25. 42 and 24 are not pretty because they don't have digits from the second list. In the second example all integers that have at least one digit different from 9 are pretty. It's obvious that the smallest among them is 1, because it's the smallest positive integer.

你被给定两个非零数字的列表。如果一个整数（以 #cf_span[10] 为基）的表示中至少包含第一个列表中的一个数字和第二个列表中的一个数字，则称其为“美观的”。求最小的正美观整数。第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 9]）——分别表示第一个和第二个列表的长度。第二行包含 #cf_span[n] 个互不相同的数字 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 9]）——第一个列表的元素。第三行包含 #cf_span[m] 个互不相同的数字 #cf_span[b1, b2, ..., bm]（#cf_span[1 ≤ bi ≤ 9]）——第二个列表的元素。请输出最小的美观整数。在第一个例子中，#cf_span[25]、#cf_span[46]、#cf_span[24567] 都是美观的，还有很多其他的整数也是。其中最小的是 #cf_span[25]。#cf_span[42] 和 #cf_span[24] 不是美观的，因为它们没有包含第二个列表中的数字。在第二个例子中，所有至少包含一个不同于 #cf_span[9] 的数字的整数都是美观的。显然，其中最小的是 #cf_span[1]，因为它是最小的正整数。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 9]）——分别表示第一个和第二个列表的长度。第二行包含 #cf_span[n] 个互不相同的数字 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 9]）——第一个列表的元素。第三行包含 #cf_span[m] 个互不相同的数字 #cf_span[b1, b2, ..., bm]（#cf_span[1 ≤ bi ≤ 9]）——第二个列表的元素。 ## Output 请输出最小的美观整数。 [samples] ## Note 在第一个例子中，#cf_span[25]、#cf_span[46]、#cf_span[24567] 都是美观的，还有很多其他的整数也是。其中最小的是 #cf_span[25]。#cf_span[42] 和 #cf_span[24] 不是美观的，因为它们没有包含第二个列表中的数字。在第二个例子中，所有至少包含一个不同于 #cf_span[9] 的数字的整数都是美观的。显然，其中最小的是 #cf_span[1]，因为它是最小的正整数。

**Definitions** Let $ A \subseteq \{1, 2, \dots, 9\} $ be the first set of distinct non-zero digits, with $ |A| = n $. Let $ B \subseteq \{1, 2, \dots, 9\} $ be the second set of distinct non-zero digits, with $ |B| = m $. **Constraints** $ 1 \leq n, m \leq 9 $, and $ A \cap B $ may be non-empty. **Objective** Find the smallest positive integer $ x $ such that the decimal representation of $ x $ contains at least one digit from $ A $ and at least one digit from $ B $.

Samples

Input #1

2 3
4 2
5 7 6

Output #1

Input #2

8 8
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Search for Pretty Integers",
    "description": {
      "content": "You are given two lists of non-zero digits. Let's call an integer pretty if its (base 10) representation has at least one digit from the first list and at least one digit from the second list. What i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF870A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two lists of non-zero digits.\n\nLet's call an integer pretty if its (base 10) representation has at least one digit from the first list and at least one digit from the second list. What i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定两个非零数字的列表。\n\n如果一个整数（以 #cf_span[10] 为基）的表示中至少包含第一个列表中的一个数字和第二个列表中的一个数字，则称其为“美观的”。求最小的正美观整数。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 9]）——分别表示第一个和第二个列表的长度。\n\n第二行包含 #cf_span[n] 个互不相同的数...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ A \\subseteq \\{1, 2, \\dots, 9\\} $ be the first set of distinct non-zero digits, with $ |A| = n $.  \nLet $ B \\subseteq \\{1, 2, \\dots, 9\\} $ be the second set of distinct non-zero...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments