Magic Trick
Time limit1sMemory limit128 MB
For each of three paragraphs, follow the rule of jumping forward by the current word's length; list all distinct outcomes in the third paragraph, or -outside- if a jump overruns the text.
- Level
Medium5 of 10
- Topics
- Simulation, Implementation, String
- Solved
- No attempts yet
Problem
Warning! This problem statement reveals the secret behind a magic trick. If you would still like to be amazed when someone shows you the trick, stop reading now.
Here is what happens. The magician shows you a text made of three paragraphs, such as:
It was a horribly dark night.
The moon was shining, but not much.
A suspicious stranger entered the
bar and went straight to John Doe.
"I'm searching for aliens, can I
borrow your computer?", he said.
He asks you to secretly pick a word in the first paragraph. Then you repeat the following two steps:
- Let be the number of characters in your current word.
- Move forward words.
Repeat until you land on a word in the third paragraph; that word is your outcome. Then you tell the magician you are done, and he reveals the word you ended on.
For this problem a word is a maximal run of letters (A-Z, a-z). For example, I'm counts as two separate words.
For instance, suppose you pick night. It has 5 characters, so you move forward five words (The, moon, was, shining, but), landing on but. From but you move 3 words to A, then 1 to suspicious, then 10 to Doe, and finally 3 to searching. searching lies in the third paragraph, so the outcome is searching.
How can the magician always know the result? Because for this text, no matter which word you start from in the first paragraph, you always end on searching. Given a new text, help the magician find every possible outcome. Besides real words, one possible outcome is -outside-, which means it is possible to jump past the end of the third paragraph. The magician is not interested if more than three different outcomes are possible.
Input
The first line contains the number of scenarios. Each scenario is given as three lines, one per paragraph. No line is longer than 100000 characters, and every paragraph contains at least one word.
Output
For each scenario, first print a line Scenario #i:, where is the scenario number starting at 1. Then print every possible outcome (possibly including -outside-) in lexicographical order, one per line and in lower case; never list an outcome more than once. If more than three outcomes are possible, print -too many- instead and none of the outcomes. After each scenario, print a blank line to separate it from the following scenario.