UVa10420 List of Conquests

Problem B
List of Conquests
Input:standardinput
Output: standard output
Time Limit: 2 seconds

In Act I, Leporello is tellingDonna Elvira about his master's long list of conquests:

``This is the list of the beauties my master has loved,a list I've made out myself: take a look, read it with me. In Italy six hundredand forty, in Germany two hundred and thirty-one, a hundred in France,ninety-one in Turkey; but in Spain already a thousand and three! Among them arecountry girls, waiting-maids, city beauties; there are countesses, baronesses,marchionesses, princesses: women of every rank, of every size, of every age.''(Madamina, il catalogo è questo)

AsLeporello records all the ``beauties'' Don Giovanni ``loved'' in chronological order,it is very troublesome for him to present his master's conquest to othersbecause he needs to count the number of ``beauties'' by their nationality eachtime. You are to help Leporello to count.

Input

Theinput consists of at most 2000lines, but the first. The first line contains a number n, indicating that there will be nmore lines. Each following line, with at most 75 characters, contains a country (the first word) and the name ofa woman (the rest of the words in the line) Giovanni loved. You may assume thatthe name of all countries consist of only one word.

Output

Theoutput consists of lines in alphabetical order. Each line starts with the nameof a country, followed by the total number of women Giovanni loved in thatcountry, separated by a space.

Sample Input

3

Spain Donna Elvira

England Jane Doe

Spain Donna Anna

Sample Output

England 1

Spain 2

---

Problem-setter:Thomas Tang, Queens University, Canada

 

 

“Failure to produce a reasonably good and error freeproblem set illustrates two things a) Lack of creativity b) Lack of commitment”

这题大意就是某个人在不同地方都有许多情人，现要求我们帮其统计他的情人都在哪个国家，及数目。这题只要用字符串读入每行的第一个单词即可，然后以一个数组来存储，同时存下其出现的次数。最后按字典序输出。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 2100;
const int M = 100;

char s[N][M];
char t[M];
int num[N];

int cmp(const void *a, const void *b) {
	return strcmp((char*)a,(char*)b);
}

int main() {
	int Case;
	
	while (cin >> Case) {
		memset(num,0,sizeof(num));
		getchar();
		for (int i = 0; i < Case; i++) {
			memset(t,0,sizeof(t));
			gets(t);
			for (int j = 0; j < M; j++) {
				if (t[j] != ' ')
					s[i][j] = t[j];
				else
					break;
			}
		}

		qsort(s,Case,sizeof(s[0]),cmp);
	
		int p = 0;
		num[p]++;
		for (int i = 1; i < Case; i++) {
			if (strcmp(s[i],s[i-1]) == 0) {
				num[p]++;
				if (i == Case-1)
					cout << s[i] << " " << num[p] << endl;
			}
			else {
				cout << s[i-1] << " " << num[p] << endl;
				p++;
				num[p]++;
				if (i == Case-1)
					cout << s[i] << " " << num[p] << endl;
			}
		}
	}
	return 0;
}