2015-16 Woburn Challenge Finals - Junior Division

Problem 2: The Oxford Comma

Knowing that the monkeys are back to take over Scarberia, Bo Vine and Old MacDonald determined that it was time to plan their defense strategy. Bo, a master tactician, knows that the best defense is a good offense. He has thus contracted the services of his good friends, the oxen, who are some of the most hardened mercenaries the world has ever seen. Bo Vine instructed the oxen to report back at once with a battle plan, consisting of a sequence of sentences. Each sentence consists of a sequence of words terminated by a single period ("."). A word is a string of non-whitespace characters (lowercase/uppercase letters from A to Z, as well as digits from 0 to 9). Words are case sensitive, so for example, "ox" and "OX" are not considered the same word. Adjacent words in any given sentence are separated by a single space. Every word in a sentence except for the last is optionally followed by a comma, which comes before the adjoining space before the next word. Every sentence ends with a period, and every sentence except for the last one is followed by a single space to separate it from the following sentence.

After slaving away through the night, the oxen were able to produce a thick stack of papers containing their battle plan, which they laid out in front of the cow lord. However, upon reading it over, Bo Vine was less than impressed by its grammar. "You call yourselves oxen? No ox of mine neglects to follow The Oxford Style Guide. Look at all of these missing Oxford commas! Just imagine if our enemies got a hold of this. They'd mock us and question your status as true oxen!"

In English language punctuation, the Oxford comma refers to the comma placed immediately before the coordinating conjunction (usually the words and or or) in a list. For example, a list of cattle breeds may be written "Jersey, Holstein and Angus" (without the Oxford comma) or "Jersey, Holstein, and Angus" (with the Oxford comma). While controversial, there are many benefits of the Oxford comma, such as resolving ambiguity. For example, Bo Vine may write his dedication of the battle plan as "To my parents, Bessie and Buttercup" or as "To my parents, Bessie, and Buttercup". The former phrase implies that he considers Bessie and Buttercup to be parental figures, while the latter phrase implies that Bessie and Buttercup are simply two other individuals to whom he's choosing to dedicate the work. For the purposes of this problem, we will always choose to follow the latter interpretation.

A list is a substring of a sentence with three or more entries in one of the following two forms:

[entry], …, [entry](,) and [entry]

or

[entry], …, [entry](,) or [entry]

where each [entry] is a single word and (,) means that the second-to-last entry on the list may or may not be immediately followed by the Oxford comma. Every other entry in the list must be directly followed by a comma, except for the last entry, which may be directly followed by a comma, period, or space. For each sentence, it is guaranteed that either there is exactly one instance of the word and (but no instances of or), exactly one instance of the word or (but no instances of and), or no instances of either word. Your task is: given the battle plan produced by Bo Vine's ox mercenaries, insert the Oxford comma into each list which is missing one. Everything else should be left the same.

Input Format

The first line of input consists of a single integer representing the number of words in the battle plan.
The second line of input contains the battle plan itself, in the format described above. The battle plan will be at most 1000 characters in length.

Output Format

Output a single line, the same battle plan but with an Oxford comma added to every list which doesn't already have one, in accordance with the specifications above.

Sample Input 1

23
Before we engage in battle, each cow soldier may choose to have spam, ham or eggs. Good luck and that will be all.

Sample Output 1

Before we engage in battle, each cow soldier may choose to have spam, ham, or eggs. Good luck and that will be all.

Sample Input 2

22
To my parents, Bessie And Buttercup. They taught me that the breakfast of a healthy cow consists of coffee, grass and toast.

Sample Output 2

To my parents, Bessie And Buttercup. They taught me that the breakfast of a healthy cow consists of coffee, grass, and toast.

All Submissions
Best Solutions


Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: May 07, 2016
Author: Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

All the test cases work


Sample input 1 has 23 words, not 24.