USACO 4.3 Letter Game

/*

ID: hubiao cave

PROG: lgame

LANG: C++

*/



#include<cstring>
#include<iostream>
#include<fstream>
#include<string>
#include<map>
#include<list>
using namespace std;



#define  VALUE(x) (value[x-‘a‘])
map<string,int> ms;
list<pair<string,string> >lp;
const int value[26]={2,5,4,4,1,6,5,5,1,7,6,3,5,2,3,5,7,2,1,2,4,6,6,7,5,7};
int evalue[26];

bool Match(string*);
int  GetValue(string*);
int  Fit(string*,string*);
bool Equal(string*);
int main()

{

    ifstream fin("lgame.in");

    ifstream fdic("lgame.dict");
    ofstream fout("lgame.out");
    string str;
    fin>>str;
    for(int i=0;i<str.length();i++)
        evalue[str[i]-‘a‘]++;
    for(fdic>>str;str!=".";fdic>>str)
        if(Match(&str))
        ms[str]=GetValue(&str);
    
    int maxv=0;
    for(map<string,int>::iterator it=ms.begin();it!=ms.end();++it)
    {
        string str=it->first;
        if(Equal(&str))
        {
            int t=GetValue(&str);
            if(maxv<t)
            {
                lp.clear();
                lp.push_back(make_pair(str,""));
                maxv=t;
            }
            else
                lp.push_back(make_pair(str,""));
            continue;
        }
        else
        {
            int t=GetValue(&str);
            if(maxv<t)
            {
                lp.clear();
                lp.push_back(make_pair(str,""));
                maxv=t;
            }
            else if(maxv==t)
                lp.push_back(make_pair(str,""));
        }
        for(map<string,int>::iterator it2=it;it2!=ms.end();++it2)
        {
            string str1=it->first,str2=it2->first;
            if(Fit(&str1,&str2))
            {
                string str3=str1+str2;
                int t=GetValue(&str3);
                if(maxv<t)
                {
                    lp.clear();
                    lp.push_back(make_pair(str1,str2));
                    maxv=t;
                }
                else if(maxv==t)
                {
                    lp.push_back(make_pair(str1,str2));
                }
            }
        }
    }

    fout<<maxv<<endl;
    for(list<pair<string,string> >::iterator it=lp.begin();it!=lp.end();it++)
    {
        fout<<it->first<<(it->second.empty()?(""):(" "+(it->second)))<<endl;
    }
    return 0;


}
bool Match(string*pstr)
{
    int ary[26];
    string str=*pstr;
    memcpy(ary,evalue,sizeof(evalue));
    for(int i=0;i<str.length();i++)
    {
        if(ary[str[i]-‘a‘]==0)
            return false;
        else
            ary[str[i]-‘a‘]--;
    }
    return true;
}
int  GetValue(string*pstr)
{
    int sum=0;
    for(int i=0;i<pstr->length();i++)
        sum+=VALUE((*pstr)[i]);
    return sum;
}
int  Fit(string* str1,string* str2)
{
    int ary[26];
    memcpy(ary,evalue,sizeof(evalue));
    for(int i=0;i<str1->length();i++)
    {
        if(ary[(*str1)[i]-‘a‘]==0)
            return false;
        else
            ary[(*str1)[i]-‘a‘]--;
    }
    for(int i=0;i<str2->length();i++)
    {
        if(ary[(*str2)[i]-‘a‘]==0)
            return false;
        else
            ary[(*str2)[i]-‘a‘]--;
    }
    return true;
}
bool Equal(string*str)
{
    int ary[26];
    memcpy(ary,evalue,sizeof(evalue));
    for(int i=0;i<str->length();i++)
            ary[(*str)[i]-‘a‘]--;
    for(int i=0;i<26;i++)
        if(ary[i]!=0)
          return false;
    return true;
}