TopCoder problem "RollingLetters" used in College Tour West China (Division I Level Three)



Problem Statement

    

A display mechanism is built from several spinning reels arranged in a line, from left to right. Each reel has a number of distinct letters on its perimeter, and only one of them is visible at a time. The visible letter changes every second. Each reel may have a different number of letters.

You are given a String[] reels, where reels[k] represents the letters on the k-th reel.

At time 0, each reel shows the letter at index 0 from the corresponding element of reels. At every second, the visible letter changes from the letter at index i to the letter at index i+1. Since reels are circular, the first letter shows up again after the last one.

Return the first second when the text displayed is equal to requiredText, or -1 if this will never happen.

 

Definition

    
Class:RollingLetters
Method:getTime
Parameters:String[], String
Returns:long
Method signature:long getTime(String[] reels, String requiredText)
(be sure your method is public)
    
 

Notes

-The return value will fit in a signed 64 bit integer.
 

Constraints

-reels will contain between 1 and 50 elements, inclusive.
-Each element of reels will contain between 2 and 26 uppercase letters ('A'-'Z'), inclusive.
-Characters in each element of reels will be distinct.
-requiredText will contain exactly N uppercase letters ('A'-'Z'), where N is the number of elements in reels.
 

Examples

0)
    
{"XYZ", "DEF", "OPRS"}
"YES"
Returns: 7
The message displayed at each second is:
0: XDO
1: YEP
2: ZFR
3: XDS
4: YEO
5: ZFP
6: XDR
7: YES
1)
    
{"ABC","ABC"}
"AB"
Returns: -1
The only possible messages are "AA", "BB", "CC".
2)
    
{"ABC"}
"X"
Returns: -1
There is no 'X' on the reel.
3)
    
{"CPKHFQEYXVMODNRTSGUBLJ", "TJLSURVHFQPAXGCEI", "JXNSGADPEWICKLFMVOQ", "UOFVKGQIJRECMWXADTPNL",
"OREWASJFLY", "HBEC", "ESDRVXCNQUFWKGTOLH", "CPLTAMBHYSQDVJIORNW", "CG"}
"CAIIEHLQC"
Returns: 4088392

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8731

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12240&pm=8731

Writer:

slex

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Math, Simulation