2046.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2046 on 2005-10-02 at 20:38:15 */ 
#include <cstdio>
#include <cstring>
#define  MAX  512

class BSTreeNode {
public:
	char content[32];
	BSTreeNode *left;
	BSTreeNode *right;
	void init(char *s) {
		left = NULL;
		right = NULL;
		strcpy(content, s);
	}
	bool search(BSTreeNode *node) {
		BSTreeNode *p = this;
		int i;
        while(true) {
            i = strcmp(node->content, p->content);
            if(i < 0) {
                if(p->left != NULL) {
                    p = p->left;
                } else {
                    p->left = node;
                    return false;
                }
            } else if(i > 0) {
                if(p->right != NULL) {
                    p = p->right;
                } else {
                    p->right = node;
                    return false;
                }
            } else {
				return true;
            }
        }
	}
};

char* slwr(char*);
long gbc(long, long);

int main() 
{ 
    char word[1024]; 
	bool find;
	long total = 0, bullNum = 0, p = 0, n;
	int i, nodeN = 0;
	BSTreeNode *Node[MAX], *root = NULL;
	
	for(i = 0; i < MAX; i++) {
		Node[i] = new BSTreeNode;
	}
    scanf("%*[^a-zA-Z]"); 
    while(scanf("%[a-zA-Z]%*[^a-zA-Z]", word) == 1) { 
        if(!strcmp(word, "BULLSHIT")) {
			total += p;
			p = 0;
			bullNum++;
			nodeN = 0;
			root = NULL;
		} else {
			slwr(word);
			Node[nodeN]->init(word);
			if(root == NULL) {
				root = Node[nodeN];
				nodeN++;
				p++;
			} else {
				find = root->search(Node[nodeN]);
				if(!find) {
					p++;
					nodeN++;
				}
			}
		}
    }
	n = gbc(total, bullNum);
	total /= n;
	bullNum /= n;
	printf("%ld / %ld\n", total, bullNum);

    return 0; 
}

char* slwr(char *s)
{
	int i;
	for(i = 0; ; i++) {
		if(s[i] >= 'A' && s[i] <= 'Z') {
			s[i] = s[i] - 'A' + 'a';
		} else if(s[i] == 0) {
			break;
		}
	}
	
	return s;
}
long gbc(long a, long b)
{
	if(b == 1) {
		return 1;
	} else if(a % b == 0) {
		return b;
	} else {
		return gbc(b, a%b);
	}
}