1539.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1539 on 2006-08-21 at 23:28:37 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 32;
const int L = 32;

class Node {
public:
	char pun[N][L];
	int n, nxt[N], total[N], nt;
	void make();
	int comp();
	void find(int, int);
};
Node node[N];
void Node::make() {
	nt = -1;
	for(n = 0; scanf("\n%[^0-9^:]", pun[n]) != 0; n++) {
		char nc[L]; scanf(":%[0-9$]", nc);
		if(nc[0] == '$') nxt[n] = -1;
		else sscanf(nc, "%d", &nxt[n]);
	}
}
int Node::comp() {
	if(nt != -1) return nt;
	memset(total, 0, sizeof(total)); nt = 0;
	for(int i = 0; i < n; i++) {
		if(nxt[i] == -1) total[i] = 1;
		else total[i] = node[nxt[i]].comp();
		nt += total[i];
	}
	return nt;
}
void Node::find(int k, int d) {
	for(int i = 0; i < n; i++) {
		if(k > total[i]) k -= total[i];
		else {
			if(d != 0) putchar('-');
			printf("%s", pun[i]);
			if(nxt[i] != -1) node[nxt[i]].find(k, d+1);
			break;
		}
	}
}

int main()
{
	while(true) {
		char cw[L];
		for(int i = 0; true; i++) {
			if(scanf("%s", cw) == EOF) return 0;
			int len = strlen(cw);
			if(cw[len-1] != ':') {
				for(int i = len-1; i >= 0; i--) ungetc(cw[i], stdin);
				break;
			} else node[i].make();
		}
		node[0].comp();
		while(true) {
			if(gets(cw) == NULL) return 0;
			else if(cw[0] == 0) break;
			int r; sscanf(cw, "%d", &r);
			node[0].find(r, 0); putchar('\n');
		}
	}
}