Diferență între revizuiri ale paginii „DSA Homework 4”
(Pagină nouă: = Word Count = Little John is learning mandarin. In order to help him look for words in a dictionary, he needs to make a list of all the new words he's encountering as he's reading a...) |
|||
| (Nu s-au afișat 3 versiuni intermediare efectuate de același utilizator) | |||
| Linia 1: | Linia 1: | ||
= Word Count = | = Word Count = | ||
| − | Little John is learning | + | Little John is learning Mandarin. In order to help him look for words in a dictionary, he needs to make a list of all the new words he's encountering as he's reading a book, but he only needs each word once. |
Help Little John make a list of all the different words in the book. | Help Little John make a list of all the different words in the book. | ||
| Linia 7: | Linia 7: | ||
== Requirement == | == Requirement == | ||
| − | Given a number of words N and a list of N words, output the number K of different words, and the list of those words, in alphabetical order. Words are considered identical only if their | + | Given a number of words N and a list of N words, output the number K of different words, and the list of those words, in alphabetical order. Words are considered identical only if their letter case matches. |
== Input Data == | == Input Data == | ||
| Linia 19: | Linia 19: | ||
== Restrictions == | == Restrictions == | ||
1 ≤ N ≤ 1000000 | 1 ≤ N ≤ 1000000 | ||
| + | |||
| + | Time complexity: O(n log n) | ||
== Examples == | == Examples == | ||
Versiunea curentă din 10 aprilie 2014 21:48
Word Count
Little John is learning Mandarin. In order to help him look for words in a dictionary, he needs to make a list of all the new words he's encountering as he's reading a book, but he only needs each word once.
Help Little John make a list of all the different words in the book.
Requirement
Given a number of words N and a list of N words, output the number K of different words, and the list of those words, in alphabetical order. Words are considered identical only if their letter case matches.
Input Data
A file called word_count.in, containing the number of words N on the first line and N subsequent words, one word per line.
Output Data
A file called word_count.out, containing the number of different words, K on the first line, then K subsequent words, alphabetically ordered, one word per line.
Restrictions
1 ≤ N ≤ 1000000
Time complexity: O(n log n)
Examples
| Input | Output |
8 Mircea a mancat cartofi si piure de cartofi |
7 Mircea a cartofi de mancat piure si |
