E. Nuclear Fusion

Codeforces

IDCF71E

Time1000ms

Memory256MB

Difficulty—

bitmasksdp

English · Original

Chinese · Translation

Formal · Original

There is the following puzzle popular among nuclear physicists. A reactor contains a set of _n_ atoms of some chemical elements. We shall understand the phrase "atomic number" as the number of this atom's element in the periodic table of the chemical elements. You are allowed to take any two different atoms and fuse a new one from them. That results in a new atom, whose number is equal to the sum of the numbers of original atoms. The fusion operation can be performed several times. The aim is getting a new pregiven set of _k_ atoms. The puzzle's difficulty is that it is only allowed to fuse two atoms into one, it is not allowed to split an atom into several atoms. You are suggested to try to solve the puzzle. ## Input The first line contains two integers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 17). The second line contains space-separated symbols of elements of _n_ atoms, which are available from the start. The third line contains space-separated symbols of elements of _k_ atoms which need to be the result of the fusion. The symbols of the elements coincide with the symbols from the periodic table of the chemical elements. The atomic numbers do not exceed 100 (elements possessing larger numbers are highly unstable). Some atoms can have identical numbers (that is, there can be several atoms of the same element). The sum of numbers of initial atoms is equal to the sum of numbers of the atoms that need to be synthesized. ## Output If it is impossible to synthesize the required atoms, print "_NO_" without the quotes. Otherwise, print on the first line «_YES_», and on the next _k_ lines print the way of synthesizing each of _k_ atoms as equations. Each equation has the following form: "_x_1_+__x_2_+_..._+__x__t__\->__y__i_", where _x__j_ is the symbol of the element of some atom from the original set, and _y__i_ is the symbol of the element of some atom from the resulting set. Each atom from the input data should occur in the output data exactly one time. The order of summands in the equations, as well as the output order does not matter. If there are several solutions, print any of them. For a better understanding of the output format, see the samples. [samples] ## Note The reactions from the first example possess the following form (the atomic number is written below and to the left of the element): To find a periodic table of the chemical elements, you may use your favorite search engine. The pretest set contains each of the first 100 elements of the periodic table at least once. You can use that information to check for misprints.

有一个在核物理学家间流行的谜题。反应堆中包含一组 #cf_span[n] 个某种化学元素的原子。我们把“原子序数”理解为该原子所属元素在元素周期表中的编号。你可以任取两个不同的原子，将它们融合成一个新的原子，其原子序数等于原两个原子序数之和。融合操作可以进行多次。目标是得到一组预先给定的 #cf_span[k] 个原子。该谜题的难点在于：只允许将两个原子融合成一个，不允许将一个原子分裂成多个原子。请你尝试解决这个谜题。第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 17]）。第二行包含空格分隔的 #cf_span[n] 个原子的元素符号，这些是初始可用的原子。第三行包含空格分隔的 #cf_span[k] 个原子的元素符号，这些是需要通过融合得到的结果。元素符号与元素周期表中的符号一致。原子序数不超过 #cf_span[100]（序数更大的元素极不稳定）。某些原子可能具有相同的序数（即可能存在多个同种元素的原子）。初始原子的序数总和等于目标原子的序数总和。如果无法合成所需的原子，请输出不带引号的 "_NO_"。否则，第一行输出 «_YES_»，接下来的 #cf_span[k] 行每行输出一个合成每个目标原子的方程式。每个方程的形式为："#cf_span[x1]_+_#cf_span[x2]_+_#cf_span[...]_+_#cf_span[xt]_->_#cf_span[yi]"，其中 #cf_span[xj] 是初始集合中某个原子的元素符号，#cf_span[yi] 是目标集合中某个原子的元素符号。输入数据中的每个原子必须在输出数据中恰好出现一次。方程中加数的顺序以及输出顺序无关紧要。如果有多个解，输出任意一个即可。为更好地理解输出格式，请参考示例。第一个示例中的反应具有以下形式（原子序数写在元素符号的左下角）：你可以使用你喜欢的搜索引擎查找元素周期表。预测试集中至少包含元素周期表前 #cf_span[100] 个元素中的每一个。你可以利用此信息检查拼写错误。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 17]）。第二行包含空格分隔的 #cf_span[n] 个原子的元素符号，这些是初始可用的原子。第三行包含空格分隔的 #cf_span[k] 个原子的元素符号，这些是需要通过融合得到的结果。元素符号与元素周期表中的符号一致。原子序数不超过 #cf_span[100]（序数更大的元素极不稳定）。某些原子可能具有相同的序数（即可能存在多个同种元素的原子）。初始原子的序数总和等于目标原子的序数总和。 ## Output 如果无法合成所需的原子，请输出不带引号的 "_NO_"。否则，第一行输出 «_YES_»，接下来的 #cf_span[k] 行每行输出一个合成每个目标原子的方程式。每个方程的形式为："#cf_span[x1]_+_#cf_span[x2]_+_#cf_span[...]_+_#cf_span[xt]_->_#cf_span[yi]"，其中 #cf_span[xj] 是初始集合中某个原子的元素符号，#cf_span[yi] 是目标集合中某个原子的元素符号。输入数据中的每个原子必须在输出数据中恰好出现一次。方程中加数的顺序以及输出顺序无关紧要。如果有多个解，输出任意一个即可。为更好地理解输出格式，请参考示例。 [samples] ## Note 第一个示例中的反应具有以下形式（原子序数写在元素符号的左下角）：你可以使用你喜欢的搜索引擎查找元素周期表。预测试集中至少包含元素周期表前 #cf_span[100] 个元素中的每一个。你可以利用此信息检查拼写错误。

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 1 \leq k \leq n \leq 17 $. Let $ A = \{a_1, a_2, \dots, a_n\} $ be the multiset of atomic numbers of the initial atoms. Let $ B = \{b_1, b_2, \dots, b_k\} $ be the multiset of target atomic numbers. Let $ S_A = \sum_{a \in A} a $, $ S_B = \sum_{b \in B} b $; given $ S_A = S_B $. Let $ \mathcal{E} $ be a bijection from atomic numbers to element symbols (periodic table mapping). **Constraints** 1. $ 1 \leq a_i \leq 100 $, $ 1 \leq b_j \leq 100 $ for all $ i, j $. 2. Each atom in $ A $ must be used exactly once in exactly one fusion chain. 3. Each target atom in $ B $ must be produced by exactly one fusion chain (a tree of fusions starting from initial atoms). 4. Fusion operation: two atoms with numbers $ x, y $ produce one atom with number $ x + y $. 5. No atom may be split. **Objective** Determine whether there exists a partition of $ A $ into $ k $ disjoint nonempty subsets $ A_1, A_2, \dots, A_k $ such that for each $ i \in \{1, \dots, k\} $: $$ \sum_{a \in A_i} a = b_i $$ If yes, output one valid sequence of fusion equations for each $ b_i $, expressing it as a sum of initial atoms (in any order), formatted as: $$ \texttt{<symbol1> + <symbol2> + \dots + <symbol_t> -> <symbol_target>} $$ where each symbol corresponds to $ \mathcal{E}(a) $ for $ a \in A_i $ and $ \mathcal{E}(b_i) $, respectively. If no such partition exists, output "_NO_".

Samples

Input #1

10 3
Mn Co Li Mg C P F Zn Sc K
Sn Pt Y

Output #1

YES
Mn+C+K->Sn
Co+Zn+Sc->Pt
Li+Mg+P+F->Y

Input #2

2 1
H H
He

Output #2

YES
H+H->He

Input #3

2 2
Bk Fm
Cf Es

Output #3

NO

API Response (JSON)

{
  "problem": {
    "name": "E. Nuclear Fusion",
    "description": {
      "content": "There is the following puzzle popular among nuclear physicists. A reactor contains a set of _n_ atoms of some chemical elements. We shall understand the phrase \"atomic number\" as the number of this a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF71E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is the following puzzle popular among nuclear physicists.\n\nA reactor contains a set of _n_ atoms of some chemical elements. We shall understand the phrase \"atomic number\" as the number of this a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有一个在核物理学家间流行的谜题。\n\n反应堆中包含一组 #cf_span[n] 个某种化学元素的原子。我们把“原子序数”理解为该原子所属元素在元素周期表中的编号。\n\n你可以任取两个不同的原子，将它们融合成一个新的原子，其原子序数等于原两个原子序数之和。融合操作可以进行多次。\n\n目标是得到一组预先给定的 #cf_span[k] 个原子。\n\n该谜题的难点在于：只允许将两个原子融合成一个，不允许将一个原子...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq n \\leq 17 $.  \nLet $ A = \\{a_1, a_2, \\dots, a_n\\} $ be the multiset of atomic numbers of the initial atoms.  \nLet $ B = \\{b_1, b_2, \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments