ZOJ Problem Set - 3045
Many media players, both software and hardware, support some kind of random mechanism, which allows the users to hear their songs in a random order. This also shows the variety of life in a special part -- few would like to listen to their songs in a fixed order every day. The most popular random mechanism is shuffle. When shuffle is turned on, the media player generates a random order (permutation) for the songs in the playlist before it is going to be played, and the songs will be played in the generated order one by one. When all songs in the list have been played, a new order is generated, and so on. Some media players also support another random mechanism named random. In this mode the player will choose a random song to be played next when the last song is finished. Some may think that random mode is not suitable for playing music since some songs may not be played forever. But obviously the probability is nearly zero, and I prefer random mode since it demonstrates the variety of life better. In this problem, given the sequence of song names you heard from the beginning, you're asked to determine which random mechanism the media player may use.
Input of each test case contains a sequence of song names. The first line contains a single integer N (1 <= N <= 10000) indicating the size of the song sequence. Each of the following N lines contains a name of a song. The names will not be empty and their lengths will not exceed 50. You can assume the names of songs in a playlist are distinct.
There's a blank line between every two successive cases. Processing to the end of file.
For each sequence, if it can only be produced in shuffle mode, print "Shuffle" in a single line; if it can only be produced in random mode, print "Random" in a single line; if it can be produced in either mode, print "Either". If neither mechanism can produce the sequence, print "Neither" instead.
4 Titanic Suite The Portrait My Heart Will Go on Epilogue - The Deep and Timeless Sea 5 1000 Words Epilogue ~Reunion~ Wind Crest ~The Three Trails~ Wind Crest ~The Three Trails~ Eternity ~Memories of Light and Waves~
Author: XIAO, Dong
Source: ZOJ Monthly, September 2008