Connection Status:
Competition Arena > DVDPlayer

DVDPlayer

SRM 263 · 2005-09-14 · by LunaticFringe

SRM 263 · 2005-09-14 · by LunaticFringe · Brute Force, Simulation
Class Name: DVDPlayer
Return Type: String[]
Method Name: findMovies
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You own a large selection of DVDs that you and your friends enjoy. Unfortunately, your friends aren't the most considerate bunch, so each DVD is not necessarily returned to its respective case. When your friends want to watch a movie, they go through each of your DVD cases one by one until they find the movie they want to watch. They then take that DVD out, and switch it with the one that's currently in the player.

You will be given a String[] moviesWatched: a list of all the movies watched in an unspecified time period, in the order they were watched. Assume you only own one copy of each movie. The DVD player is initially empty, and each DVD starts in its own case. You should return a String[] where each element describes a movie that is in a different movie's case after all DVDs in moviesWatched have been viewed. These elements should be of the format "<movie1> is inside <movie2>'s case". The list should be ordered alphabetically by the title of <movie1>. The last DVD in moviesWatched will still be in the DVD player at the end of the simulation, so it should never appear as <movie1> in the returned list.

Constraints

  • moviesWatched will contain between 2 and 50 elements, inclusive.
  • Each element of moviesWatched will contain between 1 and 20 characters, inclusive.
  • Each element of moviesWatched will consist of only lowercase letters ('a' - 'z').
  • No two consecutive elements of moviesWatched will be equal.
Examples
0)
{"citizenkane", "casablanca", "thegodfather"}
Returns: {"casablanca is inside thegodfather's case", "citizenkane is inside casablanca's case" }

Your friends first remove Citizen Kane from its DVD case and put it in the player. They then look for Casablanca, find it in its own case, and swap it with the DVD in the player. Finally, they look for The Godfather, find it in its own case, and swap it with Casablanca. Note that the output is sorted alphabetically, with "casablanca" before "citizenkane".

1)
{"starwars", "empirestrikesback", "returnofthejedi",
 "empirestrikesback", "returnofthejedi",
 "phantommenace", "starwars"}
Returns: {"empirestrikesback is inside returnofthejedi's case", "phantommenace is inside empirestrikesback's case", "returnofthejedi is inside phantommenace's case" }

After the first time your friends watch Star Wars, they put it in the Empire Strikes Back DVD case. When they want to watch it the second time, they find the case that it's in and swap it with Phantom Menace, the disk currently in the DVD player. Therefore, Phantom Menace ends up in the Empire Strikes Back's case.

2)
{"x","a","y","a","z"}
Returns: {"a is inside z's case", "x is inside a's case" }
3)
{"a", "x", "a", "y", "a", "z", "a"}
Returns: { }

All movies are back in their original cases (except movie "a", which is in the DVD player).

4)
{"ohcclzxnjjxvsfpfkzxw","dnf","ohcclzxnjjxvsfpfkzxw","kgbkcizmyuramsbkd","ohcclzxnjjxvsfpfkzxw","kgbkcizmyuramsbkd","ohcclzxnjjxvsfpfkzxw","dnf","kgbkcizmyuramsbkd","ohcclzxnjjxvsfpfkzxw","dnf","ohcclzxnjjxvsfpfkzxw","dnf","ohcclzxnjjxvsfpfkzxw","dnf","kgbkcizmyuramsbkd","dnf","ohcclzxnjjxvsfpfkzxw","dnf","kgbkcizmyuramsbkd","ohcclzxnjjxvsfpfkzxw","dnf","kgbkcizmyuramsbkd","dnf","ohcclzxnjjxvsfpfkzxw","dnf","ohcclzxnjjxvsfpfkzxw","dnf","kgbkcizmyuramsbkd","dnf","kgbkcizmyuramsbkd"}
Returns: {"dnf is inside kgbkcizmyuramsbkd's case", "ohcclzxnjjxvsfpfkzxw is inside dnf's case" }

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

Coding Area

Language: C++17 · define a public class DVDPlayer with a public method vector<string> findMovies(vector<string> moviesWatched) · 118 test cases · 2 s / 256 MB per case

Submitting as anonymous