coreBugZJ

此 blog 已弃。

Nuclear Fusion,Codeforces Beta Round #65 (Div. 2) ,E

E. Nuclear Fusion
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output



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: "x1+x2+...+xt->yi", where xj is the symbol of the element of some atom from the original set, and yi 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.



Sample test(s)
Input
10 3
Mn Co Li Mg C P F Zn Sc K
Sn Pt Y
Output
YES
Mn+C+K->Sn
Co+Zn+Sc->Pt
Li+Mg+P+F->Y

Input
2 1
H H
He
Output
YES
H+H->He

Input
2 2
Bk Fm
Cf Es
Output
NO


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.




学习了 fura2 的代码——本来只是想偷懒拷贝一下元素表的,一不小心看到了代码,于是。。。

因为学习了代码,感觉思路还是挺简单的,动态规划。。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 #include <map>
 5 
 6 using namespace std;
 7 
 8 const int N = 20;
 9 
10 int main() {
11         int n, n2, n21, k, i, j, s, t, nt;
12         static int sum[ 1<<N ], f[ 1<<N ], p[ 1<<N ];
13         string  nuclearA[ N ], nuclearB[ N ];
14         int numberA[ N ], numberB[ N ];
15 
16         map< stringint > number;
17         string nuclear[] = {
18                 "H","He","Li","Be","B","C","N","O","F","Ne","Na","Mg","Al","Si","P","S","Cl","Ar",
19                 "K","Ca","Sc","Ti","V","Cr","Mn","Fe","Co","Ni","Cu","Zn","Ga","Ge","As","Se","Br",
20                 "Kr","Rb","Sr","Y","Zr","Nb","Mo","Tc","Ru","Rh","Pd","Ag","Cd","In","Sn","Sb","Te",
21                 "I","Xe","Cs","Ba","La","Ce","Pr","Nd","Pm","Sm","Eu","Gd","Tb","Dy","Ho","Er","Tm",
22                 "Yb","Lu","Hf","Ta","W","Re","Os","Ir","Pt","Au","Hg","Tl","Pb","Bi","Po","At","Rn",
23                 "Fr","Ra","Ac","Th","Pa","U","Np","Pu","Am","Cm","Bk","Cf","Es","Fm"
24         };
25         for ( i = 0; i < sizeof(nuclear)/sizeof(nuclear[0]); ++i ) {
26                 number[ nuclear[ i ] ] = i + 1;
27         }
28 
29         cin >> n >> k;
30         n2 = ( 1 << n );
31         n21 = n2 - 1;
32         for ( i = 0; i < n; ++i ) {
33                 cin >> nuclearA[ i ];
34                 numberA[ i ] = number[ nuclearA[ i ] ];
35         }
36         for ( i = 0; i < k; ++i ) {
37                 cin >> nuclearB[ i ];
38                 numberB[ i ] = number[ nuclearB[ i ] ];
39         }
40 
41         memset( sum, 0sizeof(sum) );
42         for ( s = 0; s < n2; ++s ) {
43                 for ( j = 0; j < n; ++j ) {
44                         if ( s & (1<<j) ) {
45                                 sum[ s ] += numberA[ j ];
46                         }
47                 }
48         }
49 
50         memset( f, -1sizeof(f) );
51         f[ 0 ] = 0;
52         for ( s = 0; s < n2; ++s ) {
53                 i = f[ s ];
54                 if ( (i==-1|| (i>=k) ) {
55                         continue;
56                 }
57                 t = (s^n21);
58                 for ( j = t; j >= 0--j ) {
59                         // nt = (j&t);  // 超时
60                         nt = j = (j&t);
61                         if ( sum[ nt ] == numberB[ i ] ) {
62                                 f[ nt | s ] = i + 1;
63                                 p[ nt | s ] = s;
64                         }
65                 }
66         }
67 
68         if ( f[ n21 ] < k ) {
69                 cout << "NO" << endl;
70         }
71         else {
72                 cout << "YES" << endl;
73                 s = n21;
74                 string str;
75                 while ( s > 0 ) {
76                         i = f[ s ] - 1;
77                         t = p[ s ];
78                         str = "";
79                         for ( j = 0; j < n; ++j ) {
80                                 if ( ((s&(1<<j))!=0&& ((t&(1<<j))==0) ) {
81                                         str += nuclearA[ j ];
82                                         str += "+";
83                                 }
84                         }
85                         str.erase( str.length()-1 );
86                         str += "->";
87                         str += nuclearB[ i ];
88                         cout << str << endl;
89                         s = t;
90                 }
91         }
92 
93         return 0;
94 }
95 

posted on 2011-03-31 19:55 coreBugZJ 阅读(1274) 评论(1)  编辑 收藏 引用 所属分类: ACM

Feedback

# re: Nuclear Fusion,Codeforces Beta Round #65 (Div. 2) ,E 2011-04-01 14:15 英雄哪里出来

来踩一下~~  回复  更多评论   



只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理