A. Fingerprints

Codeforces

IDCF994A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

You are locked in a room with a door that has a keypad with 10 keys corresponding to digits from 0 to 9. To escape from the room, you need to enter a correct code. You also have a sequence of digits. Some keys on the keypad have fingerprints. You believe the correct code is the longest not necessarily contiguous subsequence of the sequence you have that only contains digits with fingerprints on the corresponding keys. Find such code. ## Input The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10$) representing the number of digits in the sequence you have and the number of keys on the keypad that have fingerprints. The next line contains $n$ distinct space-separated integers $x_1, x_2, \ldots, x_n$ ($0 \le x_i \le 9$) representing the sequence. The next line contains $m$ distinct space-separated integers $y_1, y_2, \ldots, y_m$ ($0 \le y_i \le 9$) — the keys with fingerprints. ## Output In a single line print a space-separated sequence of integers representing the code. If the resulting sequence is empty, both printing nothing and printing a single line break is acceptable. [samples] ## Note In the first example, the only digits with fingerprints are $1$, $2$ and $7$. All three of them appear in the sequence you know, $7$ first, then $1$ and then $2$. Therefore the output is _7 1 2_. Note that the order is important, and shall be the same as the order in the original sequence. In the second example digits $0$, $1$, $7$ and $9$ have fingerprints, however only $0$ and $1$ appear in the original sequence. $1$ appears earlier, so the output is _1 0_. Again, the order is important.

你被困在一个房间里，房门上有一个带有10个按键的键盘，按键对应数字0到9。要逃出房间，你需要输入正确的密码。你还拥有一个数字序列。键盘上某些按键上有指纹。你相信正确的密码是你拥有的序列中最长的（不一定连续）子序列，且该子序列仅包含具有指纹的按键对应的数字。请找出这样的密码。第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n, m lt.eq 10$)，分别表示你拥有的序列中的数字个数和键盘上有指纹的按键个数。下一行包含 $n$ 个互不相同的空格分隔整数 $x_1, x_2, dots.h, x_n$ ($0 lt.eq x_i lt.eq 9$)，表示该序列。下一行包含 $m$ 个互不相同的空格分隔整数 $y_1, y_2, dots.h, y_m$ ($0 lt.eq y_i lt.eq 9$) —— 表示有指纹的按键。请在一行中输出一个空格分隔的整数序列，表示密码。如果结果序列为空，不输出任何内容或仅输出一个换行符均可接受。在第一个例子中，唯一有指纹的数字是 $1$、$2$ 和 $7$。这三个数字都出现在你已知的序列中，顺序为先 $7$，然后 $1$，再 $2$。因此输出为 _7 1 2_。注意顺序很重要，必须与原序列中的顺序一致。在第二个例子中，数字 $0$、$1$、$7$ 和 $9$ 有指纹，但只有 $0$ 和 $1$ 出现在原序列中。$1$ 出现得更早，因此输出为 _1 0_。同样，顺序很重要。 ## Input 第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n, m lt.eq 10$)，表示你拥有的序列中的数字个数和键盘上有指纹的按键个数。下一行包含 $n$ 个互不相同的空格分隔整数 $x_1, x_2, dots.h, x_n$ ($0 lt.eq x_i lt.eq 9$)，表示该序列。下一行包含 $m$ 个互不相同的空格分隔整数 $y_1, y_2, dots.h, y_m$ ($0 lt.eq y_i lt.eq 9$) —— 表示有指纹的按键。 ## Output 请在一行中输出一个空格分隔的整数序列，表示密码。如果结果序列为空，不输出任何内容或仅输出一个换行符均可接受。 [samples] ## Note 在第一个例子中，唯一有指纹的数字是 $1$、$2$ 和 $7$。这三个数字都出现在你已知的序列中，顺序为先 $7$，然后 $1$，再 $2$。因此输出为 _7 1 2_。注意顺序很重要，必须与原序列中的顺序一致。在第二个例子中，数字 $0$、$1$、$7$ 和 $9$ 有指纹，但只有 $0$ 和 $1$ 出现在原序列中。$1$ 出现得更早，因此输出为 _1 0_。同样，顺序很重要。

Let $ S = (x_1, x_2, \dots, x_n) $ be the sequence of digits. Let $ F = \{y_1, y_2, \dots, y_m\} $ be the set of digits with fingerprints. Define the subsequence $ C = (c_1, c_2, \dots, c_k) $ as the longest subsequence of $ S $ such that for all $ c_i \in C $, $ c_i \in F $, and the elements of $ C $ appear in the same relative order as in $ S $. **Objective:** Output $ C $.

Samples

Input #1

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

Output #1

7 1 2

Input #2

4 4
3 4 1 0
0 1 7 9

Output #2

1 0

API Response (JSON)

{
  "problem": {
    "name": "A. Fingerprints",
    "description": {
      "content": "You are locked in a room with a door that has a keypad with 10 keys corresponding to digits from 0 to 9. To escape from the room, you need to enter a correct code. You also have a sequence of digits. ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF994A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are locked in a room with a door that has a keypad with 10 keys corresponding to digits from 0 to 9. To escape from the room, you need to enter a correct code. You also have a sequence of digits.\n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被困在一个房间里，房门上有一个带有10个按键的键盘，按键对应数字0到9。要逃出房间，你需要输入正确的密码。你还拥有一个数字序列。\n\n键盘上某些按键上有指纹。你相信正确的密码是你拥有的序列中最长的（不一定连续）子序列，且该子序列仅包含具有指纹的按键对应的数字。请找出这样的密码。\n\n第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n, m lt.eq 10$)，分别表示你拥有的序列中的数...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ S = (x_1, x_2, \\dots, x_n) $ be the sequence of digits.  \nLet $ F = \\{y_1, y_2, \\dots, y_m\\} $ be the set of digits with fingerprints.  \n\nDefine the subsequence $ C = (c_1, c_2, \\dots, c_k) $ as...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments