This post is written in Chinese. Please consider using Google Translate

这个题要仔细读，理解题意。起初我理解得不对，以为是输出的每个结果都必须是输入的一个排列，不能多也不能少。这种理解不正确。汗，我一直以为样例居然是错的，其实使用的字典不一样。

这道题正确的理解应该是，在结果的单词或词组构所成的字母中，每个字母出现的频数不大于输入的字符串中每个字母的频数。也就是例如输入是 aaa，字典中有单词 a,aa,aaa,aaaa，其中a,aa,aaa都是符合条件的解，但只有aaa才是要输出的最优解。

理解题意以后编程不难，直接枚举每种可行解，单词可以在O(n)内解决，词组要O(N^2)。但是对于40000个单词但是太多了。可以发现，大多数单词都是用不到的，而所以我们可以在读入字典的时候直接去除非可行解的单词，即该单词有输入字串中未出现的字母，或者在该单词中的字母中，有频数大于输入字串所含该字母频数的（例：输入字串为aabb，该单词为aaa，其中a的频数大于输入字串，必定无法有输入字串构成）。

这样优化可以去掉绝大部分的冗余，使得程序能够在很快的时间内算出结果。

所后别忘了对结果排序，可以把单词当作一个第二个单词为空串的词组，按字典顺序排序即可。

USER: CmYkRgB CmYkRgB [cmykrgb1]
TASK: lgame
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3476 KB]
   Test 2: TEST OK [0.000 secs, 3476 KB]
   Test 3: TEST OK [0.000 secs, 3476 KB]
   Test 4: TEST OK [0.011 secs, 3472 KB]
   Test 5: TEST OK [0.011 secs, 3476 KB]
   Test 6: TEST OK [0.000 secs, 3476 KB]
   Test 7: TEST OK [0.011 secs, 3472 KB]
   Test 8: TEST OK [0.011 secs, 3476 KB]
   Test 9: TEST OK [0.011 secs, 3476 KB]
   Test 10: TEST OK [0.011 secs, 3472 KB]
   Test 11: TEST OK [0.011 secs, 3472 KB]
   Test 12: TEST OK [0.011 secs, 3472 KB]

All tests OK.

Your program ('lgame') produced all correct answers!  This is your
submission #2 for this problem.  Congratulations!

/*
ID: cmykrgb1
PROG: lgame
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("lgame.in");
ifstream fd("lgame.dict");
ofstream fo("lgame.out");

typedef struct
{
    char c[7];
    int len;
    int score;
}str;

typedef struct
{
    char c1[7],c2[7];
    int len1,len2;
}Tans;

int uw['z'+1],used['z'+1];
int v['z'+1];
str S[40001];
Tans ans[50];
int N=1,L,acnt;
int Ms=0;

void init()
{
    int i;
    char c;
    bool k;
    while (!fi.eof())
    {
        c=fi.get();
        uw[c]++;
    }
    while (c!='.')
    {
        memset(used,0,sizeof(used));
        L++;
        c=fd.get();
        if (c=='.')
            break;
        k=true;
        while (c==10 || c==13)    c=fd.get();
        S[N].len=0;
        while (c!=10 && c!=13)
        {
            S[N].c[ S[N].len++ ]=c;
            used[c]++;
            if (!uw[c])
                k=false;
            c=fd.get();
        }
        S[N].c[ S[N].len ]=0;
        for (i='a';i<='z';i++)
            if (used[i]>uw[i])
            {
                k=false;
                break;
            }
        if (k)
            N++;
    }
    N--;
    v['q']=v['j']=v['z']=v['x']=7;
    v['w']=v['f']=v['k']=v['v']=6;
    v['y']=v['p']=v['g']=v['h']=v['b']=v['m']=5;
    v['u']=v['d']=v['c']=4;
    v['o']=v['l']=3;
    v['r']=v['t']=v['a']=v['n']=2;
    v['e']=v['i']=v['s']=1;
}

void findans()
{
    int i,k,p;
    for (i=1;i<=N;i++)
    {
        for (k=0;k<=S[i].len-1;k++)
            S[i].score+=v[ S[i].c[k] ];

        if (S[i].score>Ms)
        {
            Ms=S[i].score;
            acnt=1;
            for (p=0;p<=S[i].len-1;p++)
                ans[acnt].c1[p]=S[i].c[p];
            ans[acnt].len1=S[i].len;
            ans[acnt].c1[ ans[acnt].len1 ]=0;
        }
        else if (S[i].score==Ms)
        {
            acnt++;
            for (p=0;p<=S[i].len-1;p++)
                ans[acnt].c1[p]=S[i].c[p];
            ans[acnt].len1=S[i].len;
            ans[acnt].c1[ ans[acnt].len1 ]=0;
        }
    }
}

void findpair()
{
    memset(used,0,sizeof(used));
    int i,j,p;
    bool K;
    int T;
    for (i=1;i<=N-1;i++)
    {
        for (j=i+1;j<=N;j++)
        {
            T=S[i].score+S[j].score;
            for (p=0;p<=S[i].len-1;p++)
                used[S[i].c[p]]++;
            for (p=0;p<=S[j].len-1;p++)
                used[S[j].c[p]]++;
            K=true;
            for (p='a';p<='z';p++)
                if (used[p]>uw[p])
                {
                    K=false;
                    break;
                }
            memset(used,0,sizeof(used));
            if (!K) continue;
            if (T>Ms)
            {
                Ms=T;
                acnt=1;
                for (p=0;p<=S[i].len-1;p++)
                    ans[acnt].c1[p]=S[i].c[p];
                ans[acnt].len1=S[i].len;
                ans[acnt].c1[ ans[acnt].len1 ]=0;
                for (p=0;p<=S[j].len-1;p++)
                    ans[acnt].c2[p]=S[j].c[p];
                ans[acnt].len2=S[j].len;
                ans[acnt].c2[ ans[acnt].len2 ]=0;
            }
            else if (T==Ms)
            {
                acnt++;
                for (p=0;p<=S[i].len-1;p++)
                    ans[acnt].c1[p]=S[i].c[p];
                ans[acnt].len1=S[i].len;
                ans[acnt].c1[ ans[acnt].len1 ]=0;
                for (p=0;p<=S[j].len-1;p++)
                    ans[acnt].c2[p]=S[j].c[p];
                ans[acnt].len2=S[j].len;
                ans[acnt].c2[ ans[acnt].len2 ]=0;
            }
        }
    }
}


void print()
{
    fo << Ms << endl;
    int i,j;
    for (i=1;i<=acnt;i++)
    {
        for (j=0;j<=ans[i].len1-1;j++)
            fo << ans[i].c1[j];
        if (ans[i].len2)
        {
            fo << ' ';
            for (j=0;j<=ans[i].len2-1;j++)
                fo << ans[i].c2[j];
        }
        fo <<endl;
    }
}

inline int cmp(const void *a,const void *b)
{
    int k;
    Tans *A=(Tans *)a,*B=(Tans *)b;
    k=strcmp(A->c1,B->c1);
    if (k!=0) return k;
    k=strcmp(A->c2,B->c2);
    return k;
}

void sortans()
{
    qsort(ans+1,acnt,sizeof(Tans),cmp);
    print();
}

int main()
{
    init();
    findans();
    findpair();
    sortans();
    fi.close();
    fd.close();
    fo.close();
    return 0;
}