Today is the judgment day. The world is ending and all man will pay for their guilt and sin. Now the Almighty God has a long string, and some people’s name. He will take some letters from the string and use them to spell out those people’s name. What is the maximum number of the names that can be spelled, with each name be spelled at most once?
Input
The first line of input contains a number T, indicating the number of test cases. (T≤30) For each test case, the first line contains a string s, which is the string the God has. The following line contains a number n, the number of people’s names. Then n lines follow, each with a string indicating the names. There will be no more than 10 names in each test case, the length of string s will not exceed 100,000, and the length of each name will not exceed 100,000. All the strings contains lowercase letters from a to z only.
Output
For each case, output Case #i: first. (i is the number of the test case, from 1 to T). Then output a single number, as the maximum number of the people whose name can be spelled.
Sample input and output
| Sample Input | Sample Output |
|---|---|
2 |
Case #1: 0 |
Source
#include <iostream>
#include <cstring>
#include <algorithm> using namespace std; int letter[+];
int cost[+][+];
int ans;
char buffer[ + ]; int main(int argc , char * argv[])
{
int Case,T=;
scanf("%d%*c",&Case);
while(Case--)
{
memset(letter,,sizeof(letter));
memset(cost,,sizeof(cost));
int len,n;
gets(buffer);len = strlen(buffer);
for(int i = ; i < len ; ++ i )
letter[buffer[i]-'a']++;
scanf("%d%*c",&n);
for(int i = ; i < n ; ++ i)
{
gets(buffer);len = strlen(buffer);
for(int j = ; j < len ; ++ j )
cost[i][buffer[j]-'a']++;
}
int allcost[ + ];
ans = ;
for(int i = ; i < (<<n) ; ++ i)
{
memset(allcost,,sizeof(allcost));
int newans = ;
for(int j = ; j < n ; ++ j)
if ( ( i >> j ) & )
{
newans++;
for(int k = ; k < ; ++ k)
allcost[k] += cost[j][k];
}
int flag = ;
for(int j = ; j < ; ++ j)
if (allcost[j] > letter[j])
{
flag = ;
break;
}
if (flag)
ans = max(ans,newans);
}
printf("Case #%d: %d\n",T++,ans);
}
return ;
}