Statistics

Problem Statement for "TheMoviesLevelTwoDivTwo"

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.

Definition

Class:
TheMoviesLevelTwoDivTwo
Method:
find
Parameters:
int[], int[]
Returns:
int[]
Method signature:
int[] find(int[] length, int[] scary)
(be sure your method is public)

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 7 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.

Examples

  1. {100, 50}

    {1, 1}

    Returns: {0, 1 }

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

  2. {100, 50}

    {1, 49}

    Returns: {1, 0 }

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

  3. {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.

  4. {100}

    {99}

    Returns: {0 }

    Here John has no choice at all.

  5. {18, 18, 8}

    {5, 11, 6}

    Returns: {0, 1, 2 }

  6. {64}

    {55}

    Returns: {0 }

  7. {80, 30}

    {70, 1}

    Returns: {0, 1 }

  8. {27, 126, 2, 8, 38, 174, 53}

    {4, 119, 1, 3, 34, 113, 15}

    Returns: {0, 2, 1, 3, 4, 6, 5 }

  9. {185, 53, 28, 92, 70}

    {96, 17, 4, 6, 34}

    Returns: {1, 2, 3, 4, 0 }

  10. {8, 74, 12, 130}

    {3, 60, 4, 24}

    Returns: {0, 1, 2, 3 }

  11. {42, 53, 180, 154}

    {37, 33, 1, 133}

    Returns: {0, 1, 2, 3 }

  12. {32, 47, 164, 66}

    {17, 25, 35, 31}

    Returns: {0, 1, 3, 2 }

  13. {11, 196, 137, 152, 12}

    {2, 51, 46, 31, 1}

    Returns: {0, 2, 4, 1, 3 }

  14. {187, 18, 192, 144}

    {67, 10, 161, 52}

    Returns: {1, 3, 0, 2 }

  15. {2, 149, 118, 114}

    {1, 1, 64, 69}

    Returns: {0, 1, 2, 3 }

  16. {2, 90, 28, 154, 112}

    {1, 10, 17, 54, 60}

    Returns: {0, 1, 2, 4, 3 }

  17. {120, 184, 2, 38, 10}

    {1, 79, 1, 20, 5}

    Returns: {0, 2, 3, 4, 1 }

  18. {130, 54, 98, 79, 50}

    {118, 18, 6, 37, 1}

    Returns: {1, 2, 4, 0, 3 }

  19. {177, 90, 48, 132}

    {81, 54, 6, 107}

    Returns: {1, 2, 0, 3 }

  20. {58, 102, 26, 68, 71}

    {45, 49, 2, 60, 35}

    Returns: {0, 2, 3, 1, 4 }

  21. {282, 250, 330, 82, 240, 372, 33}

    {263, 108, 7, 29, 30, 180, 19}

    Returns: {3, 6, 0, 1, 2, 4, 5 }

  22. {106, 202, 124, 387, 197, 160, 244}

    {85, 100, 99, 178, 53, 100, 30}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  23. {79, 137, 357, 163, 98, 354, 310}

    {27, 100, 203, 28, 97, 153, 277}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  24. {303, 251, 307, 367, 265, 68, 300}

    {257, 36, 106, 109, 9, 4, 93}

    Returns: {5, 0, 1, 2, 3, 4, 6 }

  25. {228, 168, 6, 207, 255, 416, 81}

    {214, 140, 1, 179, 3, 96, 31}

    Returns: {2, 6, 0, 1, 3, 4, 5 }

  26. {110, 198, 470, 168, 212, 132, 366}

    {99, 41, 316, 80, 65, 38, 100}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  27. {184, 128, 75, 231, 92, 432, 402}

    {38, 1, 37, 162, 50, 307, 332}

    Returns: {2, 0, 1, 3, 4, 5, 6 }

  28. {366, 404, 167, 441, 93, 367, 455}

    {129, 250, 21, 389, 73, 138, 121}

    Returns: {4, 0, 1, 2, 3, 5, 6 }

  29. {432, 465, 210, 441, 35, 403, 32}

    {383, 268, 107, 265, 15, 112, 11}

    Returns: {4, 6, 0, 1, 2, 3, 5 }

  30. {409, 63, 453, 343, 160, 200, 143}

    {252, 45, 133, 321, 1, 109, 51}

    Returns: {1, 0, 2, 3, 4, 5, 6 }

  31. {52, 53, 56, 50, 54, 54, 56}

    {28, 1, 47, 31, 41, 21, 11}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  32. {52, 49, 48, 47, 55, 51, 47}

    {25, 46, 8, 4, 31, 29, 35}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  33. {47, 50, 50, 54, 55, 47, 47}

    {21, 38, 29, 41, 45, 15, 33}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  34. {51, 54, 55, 49, 57, 47, 48}

    {41, 37, 16, 13, 9, 34, 16}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  35. {53, 48, 51, 54, 47, 54, 49}

    {41, 40, 31, 5, 33, 29, 15}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  36. {62, 63, 66, 60, 64, 64, 66}

    {7, 23, 37, 25, 14, 19, 41}

    Returns: {0, 1, 2, 4, 3, 5, 6 }

  37. {62, 59, 58, 57, 65, 61, 57}

    {1, 16, 57, 40, 57, 49, 37}

    Returns: {2, 3, 5, 6, 1, 0, 4 }

  38. {57, 60, 60, 64, 65, 57, 57}

    {15, 55, 43, 1, 45, 17, 13}

    Returns: {0, 1, 2, 5, 6, 3, 4 }

  39. {61, 64, 65, 59, 67, 57, 58}

    {1, 47, 14, 45, 9, 46, 57}

    Returns: {0, 3, 5, 2, 4, 1, 6 }

  40. {63, 58, 61, 64, 57, 64, 59}

    {29, 34, 21, 46, 45, 3, 23}

    Returns: {0, 1, 2, 6, 5, 3, 4 }

  41. {47, 47, 47, 47, 47, 47, 47}

    {2, 45, 13, 37, 1, 17, 3}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  42. {47, 47, 47, 47, 47, 47}

    {17, 45, 3, 2, 13, 37}

    Returns: {0, 1, 2, 3, 4, 5 }

  43. {74, 74, 74, 74, 74, 74, 74}

    {71, 7, 7, 1, 21, 63, 14}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  44. {74, 74, 74, 74, 74, 74, 74}

    {38, 37, 68, 58, 18, 27, 13}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  45. {474, 474, 474, 474, 474, 474, 474}

    {382, 342, 256, 406, 439, 325, 396}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  46. {2, 2, 2, 2, 2, 2, 2}

    {1, 1, 1, 1, 1, 1, 1}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  47. {49, 72, 64, 58, 84, 84, 75}

    {48, 71, 63, 57, 83, 83, 74}

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  48. {100, 50 }

    {1, 1 }

    Returns: {0, 1 }

  49. {100 }

    {99 }

    Returns: {0 }

  50. {100, 100, 100, 100 }

    {77, 76, 75, 74 }

    Returns: {3, 0, 1, 2 }

  51. {100, 100, 100, 100, 65 }

    {78, 75, 74, 76, 20 }

    Returns: {2, 4, 0, 1, 3 }

  52. {474, 5, 10, 2, 474, 2, 74 }

    {73, 1, 6, 1, 60, 1, 73 }

    Returns: {1, 2, 3, 5, 6, 0, 4 }

  53. {250, 276, 280, 389 }

    {123, 50, 10, 364 }

    Returns: {0, 1, 2, 3 }

  54. {51, 52, 45, 50, 53, 54, 44 }

    {1, 2, 3, 4, 5, 6, 7 }

    Returns: {0, 1, 2, 3, 4, 5, 6 }

  55. {46, 49, 66, 100 }

    {45, 40, 64, 33 }

    Returns: {0, 1, 2, 3 }

  56. {100, 100 }

    {99, 99 }

    Returns: {0, 1 }

  57. {474, 123, 125, 473 }

    {87, 88, 89, 124 }

    Returns: {0, 1, 2, 3 }

  58. {121, 100 }

    {77, 99 }

    Returns: {0, 1 }

  59. {2, 2 }

    {1, 1 }

    Returns: {0, 1 }

  60. {141, 121 }

    {1, 1 }

    Returns: {1, 0 }

  61. {100, 100, 102, 100 }

    {77, 76, 75, 74 }

    Returns: {3, 0, 1, 2 }

  62. {100, 100, 100, 100, 233, 23, 34 }

    {77, 76, 75, 74, 43, 22, 12 }

    Returns: {3, 6, 5, 0, 1, 2, 4 }

  63. {121, 100, 121 }

    {77, 77, 77 }

    Returns: {0, 1, 2 }

  64. {50, 75 }

    {46, 74 }

    Returns: {1, 0 }

  65. {100, 100, 100, 100 }

    {99, 99, 99, 99 }

    Returns: {0, 1, 2, 3 }

  66. {200, 200 }

    {100, 1 }

    Returns: {0, 1 }

  67. {10, 10, 200 }

    {1, 1, 47 }

    Returns: {0, 1, 2 }

  68. {100, 100, 100, 100 }

    {73, 76, 75, 1 }

    Returns: {0, 1, 2, 3 }

  69. {100, 100, 100 }

    {99, 99, 99 }

    Returns: {0, 1, 2 }

  70. {5, 5, 5, 5 }

    {1, 3, 2, 4 }

    Returns: {0, 1, 2, 3 }

  71. {100, 80 }

    {75, 1 }

    Returns: {1, 0 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: