Connection Status:
Competition Arena > PartyGame

PartyGame

TCO05 Sponsor 2 · 2005-08-16 · by Olexiy

TCO05 Sponsor 2 · 2005-08-16 · by Olexiy · Dynamic Programming, Math
Class Name: PartyGame
Return Type: double
Method Name: numberOfMoves
Arg Types: (vector<string>, int)
Problem Statement

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.

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)
{"GRRRRRRRRRRRRGG"}
13
Returns: 14.0
3)
{"GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"}
1
Returns: 49.0
4)
{"GRRRRRRRRRRRRG"}
13
Returns: 13.0

Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PartyGame with a public method double numberOfMoves(vector<string> field, int N) · 65 test cases · 2 s / 256 MB per case

Submitting as anonymous