DevuAndGame
SRM 666 · 2015-06-30 · by praveen123
Problem Statement
Devu loves to play games.
This problem is about a game he recently played.
In the game there are n locations, numbered 0 through n-1.
Each location has one entrance and one exit.
You are given a
Devu started the game by entering location 0. Return "Win" (quotes for clarity) if he can win the game. Otherwise, return "Lose". Note that the return value is case-sensitive.
Constraints
- nextLevel will have between 1 and 50 elements, inclusive.
- Each element in nextLevel will be either -1 or will be between 0 and n - 1, inclusive.
{1, -1}
Returns: "Win"
Devu will start in location 0. The exit from this location will bring him to location 1, and when he reaches the exit from location 1 he wins the game.
{1, 0, -1}
Returns: "Lose"
Devu will go back and forth between locations 0 and 1. He is unable to reach the exit from location 2.
{0, 1, 2}
Returns: "Lose"
The exit from location 0 leads back to location 0. Devu is unable to reach the other locations.
{29,33,28,16,-1,11,10,14,6,31,7,35,34,8,15,17,26,12,13,22,1,20,2,21,-1,5,19,9,18,4,25,32,3,30,23,10,27}
Returns: "Win"
There can be multiple x such that nextLevel[x] is -1. In order to win the game, Devu has to reach any single location with this property.
{17,43,20,41,42,15,18,35,-1,31,7,33,23,33,-1,-1,0,33,19,12,42,-1,-1,9,9,-1,39,-1,31,46,-1,20,44,41,-1,-1,12,-1,36,-1,-1,6,47,10,2,4,1,29}
Returns: "Win"
{3, 1, 1, 2, -1, 4}
Returns: "Lose"
In this game, Devu will go from location 0 to location 3, from there to location 2, and from there to location 1. There he will get stuck, as the exit from location 1 leads back to location 1.
Submissions are judged against all 109 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DevuAndGame with a public method string canWin(vector<int> nextLevel) · 109 test cases · 2 s / 256 MB per case