J. Polycarp and Dividend

Codeforces

IDCF10083J

Time3000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Polycarp have free time, collection of N decimal digits c1, ... , cN and positive integer A. He wants to find positive integer B, such that A divides B and B contains only digits from collection c1, ... , cN. Each digit from collection can be used any times. It is not required to use all the digits. The first line contains N — the number of digits in collection, 1 ≤ N ≤ 10. The second line contains N integer numbers ci (0 ≤ ci ≤ 9). Each digit can be there at most one time. The third line contains integer A, 1 ≤ A ≤ 105. Output B. If you cannot find it, then output _-1_. ## Input The first line contains N — the number of digits in collection, 1 ≤ N ≤ 10. The second line contains N integer numbers ci (0 ≤ ci ≤ 9). Each digit can be there at most one time. The third line contains integer A, 1 ≤ A ≤ 105. ## Output Output B. If you cannot find it, then output _-1_. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $, $ 1 \leq N \leq 10 $, be the number of available digits. Let $ D = \{c_1, c_2, \dots, c_N\} \subseteq \{0,1,\dots,9\} $ be the set of available digits. Let $ A \in \mathbb{Z}^+ $, $ 1 \leq A \leq 10^5 $, be the given divisor. **Constraints** - All $ c_i \in D $ are distinct. - $ B \in \mathbb{Z}^+ $ must satisfy: 1. $ A \mid B $, 2. Every digit of $ B $ (in decimal representation) belongs to $ D $. **Objective** Find the smallest such $ B $, or output $-1$ if no such $ B $ exists.

API Response (JSON)

{
  "problem": {
    "name": "J. Polycarp and Dividend",
    "description": {
      "content": "Polycarp have free time, collection of N decimal digits c1, ... , cN and positive integer A. He wants to find positive integer B, such that A divides B and B contains only digits from collection c1, .",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10083J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp have free time, collection of N decimal digits c1, ... , cN and positive integer A. He wants to find positive integer B, such that A divides B and B contains only digits from collection c1, ....",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $, $ 1 \\leq N \\leq 10 $, be the number of available digits.  \nLet $ D = \\{c_1, c_2, \\dots, c_N\\} \\subseteq \\{0,1,\\dots,9\\} $ be the set of available digits. ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments