1656.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1656 on 2005-11-22 at 15:53:31 */ 
#include <cstdio>
#include <cstring>

const int MAX = 102400;

class Paragraph {
private:
	bool isAlpha(char&) const;
public:
	char line[MAX];
	int n;
	char *word[MAX];
	void parse();
};
bool Paragraph::isAlpha(char& c) const {
	if(c >= 'a' && c <= 'z') {
		return true;
	} else if(c >= 'A' && c <= 'Z') {
		c -= 'A' - 'a';
		return true;
	} else {
		return false;
	}
}
void Paragraph::parse() {
	bool begin = false;
	int i;
	n = 0;
	for(i = 0; line[i] != '\0'; i++) {
		if(isAlpha(line[i])) {
			if(!begin) {
				begin = true;
				word[n++] = line + i;
			}
		} else {
			begin = false;
			line[i] = '\0';
		}
	}
}

class Stack {
public:
	int n;
	char word[4][MAX];
	void insert(const char*);
	void sort();
};
void Stack::insert(const char *s) {
	int i;
	for(i = 0; i < n; i++) {
		if(!strcmp(word[i], s)) {
			return;
		}
	}
	strcpy(word[n++], s);
}
void Stack::sort() {
	int i, j;
	for(i = 0; i < n; i++) {
		for(j = n-1; j >= 1; j--) {
			if(strcmp(word[j], word[j-1]) < 0) {
				char t[MAX];
				strcpy(t, word[j]);
				strcpy(word[j], word[j-1]);
				strcpy(word[j-1], t);
			}
		}
	}
}

Paragraph para[3];
Stack stack;

int main()
{
	int T, t;
	int i, j, k, l;
	int reach[2][MAX];
	bool reached[MAX], out;
	
	//freopen("E:\\1\\magic.in", "r", stdin);
	//freopen("E:\\1\\magicw.out", "w", stdout);
	scanf("%d", &T);
	getchar();
	for(t = 1; t <= T; t++) {
		for(i = 0; i < 3; i++) {
			gets(para[i].line);
			para[i].parse();
		}
		printf("Scenario #%d:\n", t);
		for(i = 1; i >= 0; i--) {
			for(j = para[i].n-1; j >= 0; j--) {
				l = strlen(para[i].word[j]);
				int o = j + l;
				for(k = i; k < 2 && o >= para[k].n; k++) {
					o -= para[k].n;
				}
				if(k == 2) {
					reach[i][j] = o;
				} else {
					reach[i][j] = reach[k][o];
				}
			}
		}
		stack.n = 0;
		memset(reached, false, sizeof(reached));
		out = false;
		for(i = 0; i < para[0].n; i++) {
			if(stack.n > 3) {
				break;
			} else if(reach[0][i] >= para[2].n && !out) {
				stack.insert("-outside-");
				out = true;
			} else {
				if(!reached[reach[0][i]]) {
					stack.insert(para[2].word[reach[0][i]]);
					reached[reach[0][i]] = true;
				}
			}
		}
		if(stack.n > 3) {
			printf("-too many-\n");
		} else {
			stack.sort();
			for(i = 0; i < stack.n; i++) {
				printf("%s\n", stack.word[i]);
			}
		}
		putchar('\n');
	}
	
	return 0;
}