2077.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2077 on 2005-12-03 at 20:40:09 */ 
#include <cstdio>
#include <cstring>

const int T_MAX = 128;
const int N_MAX = 32;
const char size[] = "SMLXT";

int shirt[5], n;
bool suit[N_MAX][5];

int search(char);
bool DFS(int);

int main()
{
	char info[N_MAX];
	int i, j, p;
	bool can;
	
	while(scanf("%s", info) != EOF && strcmp(info, "ENDOFINPUT")) {
		memset(suit, false, sizeof(suit));
		memset(shirt, 0, sizeof(shirt));
		can = true;
		scanf("%d", &n);
		for(i = 0; i < n; i++) {
			scanf("%s", info);
			int begin = search(info[0]);
			int end = search(info[1]);
			for(j = begin; j <= end; j++) {
				suit[i][j] = true;
			}
			if(begin == end) {
				shirt[begin]--;
				n--;
				i--;
			}
		}
		for(i = 0; i < 5; i++) {
			scanf("%d", &p);
			shirt[i] += p;
			if(shirt[i] < 0) {
				can = false;
			}
		}
		if(can && DFS(0)) {
			printf("T-shirts rock!\n");
		} else {
			printf("I'd rather not wear a shirt anyway...\n");
		}
		scanf("%*s");
	}
	
	return 0;
}

int search(char s)
{
	int i;
	for(i = 0; size[i] != 0; i++) {
		if(size[i] == s) {
			return i;
		}
	}
	return -1;
}
bool DFS(int d)
{
	if(d == n) {
		return true;
	} else {
		int i;
		for(i = 0; i < 5; i++) {
			if(suit[d][i] && shirt[i] > 0) {
				shirt[i]--;
				if(DFS(d+1)) {
					return true;
				} else {
					shirt[i]++;
				}
			}
		}
		return false;
	}
}