Problem B: Conformity

University administrators are uncomfortable with this situation, andtherefore wish to offer a conformity prize to frosh who choosethe most popular combination of courses. How many frosh will winthe prize?

The input consists of several test cases followed by a line containing0. Each test case begins with an integer 1 ≤ n ≤ 10000, the number offrosh. For each frosh, a line follows containing the course numbersof five distinct courses selected by the frosh. Each course number isan integer between 100 and 499.

The popularity of a combination is the number of frosh selectingexactly the same combination of courses. A combination of coursesis considered most popular if no other combination has higherpopularity. For each line of input, you should output a single linegiving the total number of students taking some combination of courses thatis most popular.

Sample Input

3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100
3
200 202 204 206 208
123 234 345 456 321
100 200 300 400 444
0

Output for Sample Input

2
3

最受歡迎的組合可能有很多, 輸出選擇最受歡迎組合的人數

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct  Trie {
	int n;
	int link[10];
}Node[200000];
int TrieSize;
void insertTrie(const char* str) {
	static int i, idx;
	idx = 0;
	for(i = 0; str[i]; i++) {
		if(Node[idx].link[str[i]-'0'] == 0) {
			TrieSize++;
			memset(&Node[TrieSize], 0, sizeof(Node[0]));
			Node[idx].link[str[i]-'0'] = TrieSize;
		}
		idx = Node[idx].link[str[i]-'0'];
	}
	Node[idx].n ++;
}
int max, maxNum;
void findAns(int now) {
	if(Node[now].n != 0) {
		if(max == Node[now].n) {
			maxNum += Node[now].n;
		} else if(max < Node[now].n){
			max = Node[now].n;
			maxNum = max;
		}
	}
	int i;
	for(i = 0; i < 10; i++) {
		if(Node[now].link[i] != 0) {
			findAns(Node[now].link[i]);
		}
	}
}
int cmp(const void *i, const void *j) {
	return *(int *)i - *(int *)j;
}
int main() {
	int n, A[5];
	char buf[20];
	while(scanf("%d", &n) == 1 && n) {
		TrieSize = 0;
		memset(&Node[0], 0, sizeof(Node[0]));
		while(n--) {
			scanf("%d %d %d %d %d", &A[0], &A[1], &A[2], &A[3], &A[4]);
			qsort(A, 5, sizeof(int), cmp);
			sprintf(buf, "%d%d%d%d%d", A[0], A[1], A[2], A[3], A[4]);
			insertTrie(buf);
		}
		max = 0, maxNum = 0;
		findAns(0);
		printf("%d\n", maxNum);
	}
    return 0;
}