UVa : 895 (Word Problem)



// http://uva.onlinejudge.org/external/8/895.html
// Runtime : 0.012s
// Tag : ad-hoc

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

char a [1000 + 3] [10 + 3];
int tmp [26];

bool can_make (int p)
{
	int len = strlen (a [p]);
	bool ret = true;

	for ( int i = 0; i < len; i++ ) {
		if ( tmp [a [p] [i] - 'a'] == 0 ) ret = false;
		tmp [a [p] [i] - 'a']--;
	}

	return ret;
}
int main ()
{
	int words = 0;

	while ( gets (a [words]) && strcmp (a [words], "#") != 0 ) words++;

	char input [1000];

	while ( gets (input) && strcmp (input, "#") != 0 ) {
		int frq [26];
		memset (frq, 0, sizeof (frq));
		int len = strlen (input);

		for ( int i = 0; i < len; i++ ) {
			if ( isalpha (input [i]) )
				frq [input [i] - 'a']++;
		}

		int cnt = 0;

		for ( int i = 0; i < words; i++ ) {
			for ( int j = 0; j < 26; j++ ) 
				tmp [j] = frq [j];
			if ( can_make (i) ) cnt++;
		}

		printf ("%d\n", cnt);

	}

	return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s