Bingo, Really?!
Time limit1sMemory limit128 MB
Split the input into letter-only words, count distinct words per game ending at BULLSHIT, and print the running average as an irreducible fraction.
- Level
Medium4 of 10
- Topics
- String, Hash map, Implementation, Math
- Solved
- No attempts yet
Problem
Daehyeok is a teacher, but his classes are terribly boring. So his students secretly started playing bingo during class. Daehyeok, however, is sharp and already knew all about it. Before scolding them, he wants to find out how many words a single game of bingo takes on average.
Every word the students call out consists only of English letters, and both uppercase and lowercase letters may be used. To confuse Daehyeok, the students sometimes insert non-letter characters at the beginning, middle, or end of a word. Therefore each maximal run of consecutive letters is a single word, and any non-letter character acts as a separator. For example, object-oriented counts as the two words object and oriented, and types: counts as the single word types.
When a student completes a bingo, they shout BULLSHIT, and Daehyeok knows from this shout that one game has ended. Within a single game, if the same word is called several times it still counts once. Letters are case-insensitive, so Bingo and bingo are the same word.
Based on how many distinct words are called in each game, compute the average number of words per game.
Input
The input consists of several sentences with BULLSHIT mixed in between them. Each BULLSHIT signals that one game has ended.
The input obeys the following rules.
BULLSHITis always given in uppercase and marks the end of a game. (A lowercasebullshitand the like are treated as ordinary words.)- Each word is at most 25 letters long, and each sentence is at most 100 characters long.
- Before a game ends, at most 500 distinct words appear.
- Inputs where a game cannot be formed are never given, so you do not need to check for them.
The input continues until end of file. Any words left after the final BULLSHIT form a game that has not finished yet and are not included in the average.
Output
Each time a game ends, sum the number of distinct words called in that game, then divide that total by the number of finished games and print the average.
Print the answer as an irreducible fraction (not a decimal), where the greatest common divisor of the numerator and denominator is 1. The output format is numerator / denominator, with a single space on each side of the slash. Even when the value is an integer, append a denominator of 1 and print it as integer / 1.
For example, if 10 games were played and 55 words were called in total, reduce and print 11 / 2.