TopCoder problem "PartyGame" used in TCO05 Round 2 (Division I Level Two)



Problem Statement

    You are playing a one-player game. The board for the game consists of several red and green cells ordered in a row. Initially you are located at the first cell. On each move, you roll an N-sided die with numbers from 1 to N on its sides and move the corresponding number of cells ahead. If you stop on a red cell, you jump back to the cell you started the move from. If you stop at green, you stay there. You win the game when you jump on the last cell or pass it by.



Given a String[] field, return the expected number of moves you will need to win the game (return -1 if you will never win). All characters in all elements of field will be either 'G' or 'R', for green and red cells respectively. The first character of the first element of field represents the cell where you are located at the start of the game. The last character of the last element of field represents the last cell. You should concatenate all Strings from field to get the complete game field.
 

Definition

    
Class:PartyGame
Method:numberOfMoves
Parameters:String[], int
Returns:double
Method signature:double numberOfMoves(String[] field, int N)
(be sure your method is public)
    
 

Constraints

-field will contain between 1 and 50 elements, inclusive.
-Each element of field will contain between 1 and 50 characters, inclusive.
-The total number of characters in the field must be at least 2.
-Each element of field will contain only 'R' and 'G' characters.
-The first character of the first element of field and the last character of the last element of field will both be 'G'.
-N will be between 1 and 20, inclusive.
 

Examples

0)
    
{"GRG"}
2
Returns: 2.0
1)
    
{"GRRG"}
2
Returns: -1.0
2)
    
{"GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"}
6
Returns: 14.47619043642061
3)
    
{"GGRRRGRGRRGRRRGRRRRRRRRRRRGRRGRRRRRRRGRRRRRR",
 "RRRRRRRRRRRRRRRRRGRRRRRRRRRRRRGRRRRGRRRRRGRGR",
 "RRRGRRRRRRGGRRRRRRRRRRRRRRGRRRGRRRRRRGRRRRRRGR",
 "RRGRRRRGRRRRGRGRRRRRRRGRRGRRRRRRRRRRRRRRGRRRGGG",
 "RRRRRRRRRRRRRRRGRRGRRRRRRGRRRRRRRRGRRRRRRRRRRGRR",
 "GRRRRRGGGRRRRRGRRRRRRRRRRRGRRRRRRRGRRGRRRRRRRRRRR",
 "RRRRRRRRGGGGGGGGRRRRRRRRRRRRRRRRRRGRRRRRRRRGGGGGGG",
 "GGGGGGGGGRRRRRRRRRRRRRRRRRRGRRRRRRRRRRRRRRRRRRGRRR",
 "RRRRRGRGRRRRRRRRRRRRRRRGRRRRRRRRRRRGRRRRRRRRRRRRRG",
 "GRRRRRRRRRRRRRRRRRRGRRRRRRRRRRRRRRRGRRRGRRRRRRRRGR",
 "RRRRRRGRRGRRRRRRGRRRRRRRRRRRRRRRRGRGRGRRRRRRGRRRRG",
 "RGRRRRRRRRRGRRGRRRRRRGRRRRRRRGRRGRRGRGGGGGGGGRRRRR",
 "RRRRRRRRRRRRRGRRRRRRRRRGRRRRRRRRRRGRRRRRRGGGGGGGGG",
 "GGGGGGGGGGGGGGGGGGGGGGGGGGGGRRRRRRRRRRRRRRRRRRGGGG",
 "GRRRRRRRRRRRRRRRRRRGRRRGGGGGGGGGGRRRRRRRRRRRRRRRRR",
 "RGGGGGGGGGGGGGGGGGGGGGGGGGGRRRRRRRRRRRRRRRRRRGRRRR",
 "RRRGRRRRRRRRRGRRRRRRRRRRRGRRRRRRRRRRRRRRGRRRRRRRGG",
 "RRRRGGGGGGGGGGRRRRRRRRRRRRRRRRRRGGRRRGRGRRRRRRRRRR",
 "RRRRRGRRRRRRRRRGRGRRGRRGRRRRRRRRRRRRRRRRGGRRGRRRRR",
 "RRRRRRGRRRRRRRRRGGRRRRRGRRRRGRRRRRRRRGGRRRRRRRRRGR",
 "RRRGRRRRRRRRRRRRRRGGGRRRRRRRGRRRRRRRRRRRRRRRRGGGGG",
 "GGGGGGGRRRRRRRRRRRRRRRRRRGRRRGRRRRRRRRRRRRRGGRRRRG",
 "GRRRRRRRRRRRGRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGGGGG",
 "GGGGGGGGGGGGGGGRRRRRRRRRRRRRRRRRRGRRRRGGGGGGGGGGGR",
 "RRRRRRRRRRRRRRRRRGRRGRRGRRRRRGRRGRRRRRRRRRGRRRRRRR",
 "RRRRRRGGGGGGGGGGGGGGRRRRRRRRRRRRRRRRRRGRRRRRRRRRRG",
 "RRRRRRRRRGRRRRRRRRRRRRRRRRGRGRRRRRRRRRRGRRRRRRGRRR",
 "RRRRRRRRRGGRRRRRRRRRRRRRRRRRRGRRRRRGRRRRGRRRRRGRRR",
 "RRRGRRGRRRGRRRRRRRRRRGRRRRRRRRRRGGRRRRRRGGRRRRRRRR",
 "RRGRRRRRRRRRRRRGRGRRRGGRGRRGRRRGRRRRRRRRRRRGRRRRRR",
 "RGRRRRRRRRRRRRRGGRRRRRRRRRGRRRGRRRRRRRRRGRRRRGGRRR",
 "RRRRRRRRRRRRRRRGRRRRRRRRRGRGRRRRGGGGGGGGGRRRRRRRRR",
 "RRRRRRRRRGRRRRRRGRRRRRRRRRRGRRRRRRRGRRRRRRRRRRRRRR",
 "RRGRRRRRRRRRRRRRRRRRRGRRRRRRRRGRRRRGRGRRRRRRRRRRRG",
 "RGRRGRRRGRRRRRGRRRRRRRRRGRRRRRRRRRRGRRGRRRRRRRGRGG",
 "GRRRRRRRRRRRRRRRRRRGRRRRRRRRRRRRRRRRRGRRRRRRRGRRRR",
 "RRRRRGRRRRRRRGRGRRRRRRRRGGRRRRRRGRRRRRRRRRRRRGRRRR",
 "RRGRRRRRRRRRRRGRRGRRRRRRRRRRGRRRRRRRRRGRRRGRGRRGRR",
 "RRRRGRRRRRRRRRRGRRRRRRRRRRRRRRRGRRRRRRRGRRGGGGGGGG",
 "GGGGGGGGGGGGGGGGGGGGGGGGGGGGRRRRRRRRRRRRRRRRRRGRRR",
 "RGGRGGGGRRRRRRRRRRRRRRRRRRGRGRRRGGRRRRRRGGRRRRRRRG",
 "RRRRGRRRRRRRRRRRRGGGGGGRRRRRRRRRRRRRRRRRRGRRRRRRRR",
 "RRRRRRRGRRRRRRRRRRGRRGGGGGGGGGGGGGRRRRRRRRRRRRRRRR",
 "RRGRRRRRRRRRRRRRRRGGRRGRRRRGRRRRGRRRRRRRRRRRRGRGRG",
 "RGRRRRRRRGRRRRRRRGRRRGGRRRRRRRRGRRRRRRRRRGGGRRRRRR",
 "GGGGGGRRRRRRRRRRRRRRRRRRGRGRRRRRRRRRRRGRRRRRRGRRRR",
 "RRRRRRRGRRRRRRRRGRRRRRRRRRRRRRGGRRRRRRRRRRRRRRRRGR",
 "RRRRRRRRRRRRRGRRRRRRRRRRRRRRRRRGRRRRGRRRRRRRRRRGRR",
 "RRRRGRGRRRRRRRRGRRRRRGRRRRRRRRRRRRRRRGRRRRRRGRRRRR",
 "RRGRRGRRRRRRRGGRRGRRRRRRGRRRRRRRRRRRRRRRRRGRGRRRRG"}
19
Returns: -1.0

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8017&pm=4635

Writer:

Olexiy

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming, Math