• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(1521) 評論(1)  編輯 收藏 引用 所屬分類: ACM

            Feedback

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

            來踩一下~~  回復  更多評論   


            国内精品久久久久久久影视麻豆| 婷婷久久香蕉五月综合加勒比 | 亚洲综合日韩久久成人AV| 香蕉久久久久久狠狠色| 久久青青草原亚洲av无码app| 久久国产精品成人影院| 欧美精品丝袜久久久中文字幕| 久久这里的只有是精品23| 77777亚洲午夜久久多喷| 久久精品国产亚洲7777| 亚洲综合伊人久久综合| 久久久久久国产精品免费免费 | 久久综合狠狠综合久久| 日韩久久无码免费毛片软件 | 伊人伊成久久人综合网777| 久久综合久久久| 亚洲精品乱码久久久久久蜜桃图片| 99久久精品费精品国产一区二区| 色婷婷狠狠久久综合五月| 久久久精品免费国产四虎| 无码精品久久久久久人妻中字| 久久久精品久久久久久| 午夜不卡888久久| 2020久久精品国产免费| 伊人久久大香线蕉AV色婷婷色| 久久精品国产72国产精福利| 国产成人久久精品区一区二区| 伊人久久大香线蕉亚洲| 久久人人爽人人爽人人片AV高清| 国产农村妇女毛片精品久久| 国内精品伊人久久久久| 久久99久久99精品免视看动漫| 久久天天躁夜夜躁狠狠躁2022| 欧美午夜A∨大片久久 | 久久精品国产亚洲欧美| .精品久久久麻豆国产精品| 国产成人无码久久久精品一| 97精品久久天干天天天按摩| 久久99国产精品久久99| 日本福利片国产午夜久久| 色噜噜狠狠先锋影音久久|