Connection Status:
Competition Arena > RoadSigns

RoadSigns

SRM 83 · 2002-04-27 · by wyzmo

SRM 83 · 2002-04-27 · by wyzmo
Class Name: RoadSigns
Return Type: String
Method Name: play
Arg Types: (vector<string>)
Problem Statement

Problem Statement

A game that can be played while traveling by automobile is to try to find the 26 letters of the alphabet contained in road signs passed on the way. Start with the letter 'A'. If the letter 'A' is found in a road sign, look for the letter 'B'. Proceed through the consecutive letters of the alphabet in this manner until all of the letters are found. The following rules apply:

  • More than one letter can be found in the same sign.
  • Letters within a sign do not have to appear in alphabetic sequence.
  • Once a sign is passed it cannot be used again.
  • Once all the letters of the alphabet are found ending with the letter 'Z', the game ends.

Write a method that, given a String[] whose elements represent road signs in the order they are seen, examines each sign and returns the last letter found and the zero based index of the sign containing that last letter as a String in the form "cn" where 'c' represents the letter, and 'n' represents the index. If no letter is found, that is, the letter 'A' does not appear in the signs, or if there are no signs at all, return "" (the empty string).

Constraints

  • signs contains between 0 and 20 elements, inclusive.
  • the length of each element of signs is between 1 and 50 characters, inclusive.
  • each element of signs contains only uppercase letters ('A'-'Z'), digits ('0'-'9'), and the space character (' ').
Examples
0)
{}
Returns: ""
1)
{"STOP","YIELD"}
Returns: ""
2)
{"FALLING ROCK","SCHOOL BUS STOP AHEAD","SPEED LIMIT 15"}
Returns: "E1"

There are three signs. Start looking for the letter 'A'. The first sign, "FALLING ROCK", contains the letter 'A'. Now start looking for the letter 'B'. "FALLING ROCK" does not contain a 'B' so move on to the next sign. "SCHOOL BUS STOP AHEAD" does contain a 'B' . Now look for a 'C'. "SCHOOL BUS STOP AHEAD" also contains a 'C'. So look for a 'D', again found in "SCHOOL BUS STOP AHEAD". 'E' is also found. Now look for 'F'. "SCHOOL BUS STOP AHEAD" does not contain an 'F', so move on to the next sign. (Note that the 'F' contained in "FALLING ROCK" cannot be used because that sign has already been passed.) The third sign, "SPEED LIMIT 15", does not contain an 'F'. There are no more signs. The last letter found was the letter 'E' in "SCHOOL BUS STOP AHEAD" at index 1, so the method returns the result "E1".

3)
{"BRIDGE FREEZES BEFORE ROAD SURFACE","EXIT 8 HEBRON AVENUE"}
Returns: "I1"
4)
{"A","B","C","D","E","F","G","H","I","J","K","L","M","X","Y","Z"}
Returns: "M12"

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

Coding Area

Language: C++17 · define a public class RoadSigns with a public method string play(vector<string> signs) · 39 test cases · 2 s / 256 MB per case

Submitting as anonymous