Connection Status:
Competition Arena > TheMoviesLevelTwoDivOne

TheMoviesLevelTwoDivOne

SRM 469 · 2009-11-12 · by Vasyl[alphacom]

SRM 469 · 2009-11-12 · by Vasyl[alphacom] · Dynamic Programming
Class Name: TheMoviesLevelTwoDivOne
Return Type: int[]
Method Name: find
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

John has decided to watch some horror movies tonight. He has a collection of N scary movies, numbered 0 to N-1, inclusive. The lengths of the movies are given in the int[] length, where the i-th element is the length in minutes of movie i.

However, John is very tired, so it is possible for him to fall asleep while watching a movie. The only way he can stay awake is to maintain a certain level of being scared. He has a "scare level" which is a real number initially equal to 74. His scare level will continuously decrease at a speed of 1 per minute. For example, after 6 seconds, it will go down by 0.1. Once this level falls below -0.5, John will fall asleep. Each of John's movies has exactly one scary moment. Once John sees this moment, his scare level will instantly increase by 47. The scary moments are given in the int[] scary. In movie i, the scary moment will occur exactly scary[i] minutes after the beginning of the movie.

John would like to determine the best order in which to watch the movies. Each order can be described by an int[] containing N distinct numbers between 0 and N-1, inclusive. The first element is the number of the first movie he watches, the second element is the number of the second movie he watches, and so on. Once a movie is finished playing, the next one starts immediately. If John falls asleep while watching a movie, he won't be able to watch the rest of the current movie, and he won't be able to watch any of the movies that he planned to watch after the current movie. Among all the possible orders, return the one that allows John to watch as many movies as possible in their entirety (i.e., from beginning to end) before falling asleep. If there are several such orders, return the one that comes earliest lexicographically.

Notes

  • A int[] A comes before a int[] B lexicographically if A contains a smaller number at the first index where they differ.

Constraints

  • length will contain between 1 and 20 elements, inclusive.
  • length and scary will contain the same number of elements.
  • Each element of length will be between 2 and 474, inclusive.
  • The i-th element of scary will be between 1 and length[i] - 1, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{100, 50}
{1, 1}
Returns: {0, 1 }

There are two possible playlists, and John can watch either one in its entirety without falling asleep.

1)
{100, 50}
{1, 49}
Returns: {1, 0 }

The only way John can see all the movies is to start with the last one.

2)
{100, 100, 100, 100}
{77, 76, 75, 74}
Returns: {3, 0, 1, 2 }

If John starts with the last movie, he will fall asleep during the second movie. If he starts with any other movie, he will fall asleep during the first movie.

3)
{100}
{99}
Returns: {0 }

Here John has no choice at all.

4)
{18, 18, 8}
{5, 11, 6}
Returns: {0, 1, 2 }

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

Coding Area

Language: C++17 · define a public class TheMoviesLevelTwoDivOne with a public method vector<int> find(vector<int> length, vector<int> scary) · 151 test cases · 2 s / 256 MB per case

Submitting as anonymous