Statistics

Problem Statement for "SandTimers"

Problem Statement

Sigh... If only the king could make up his mind. First he wanted rounds in the Royal Wrestling Tournament to last for 2 minutes, then he changed his mind to 3 minutes. He wanted periods in the Royal Hockey Tournament to last for 20 minutes, then he decided on 15. Your job as the Royal Time Keeper would be much easier if he would buy you a modern stopwatch, but he insists that you use the Royal Sand Timers, which have been in his family since the 14th century. You're worried that someday he is going to ask you to measure a time interval that simply can't be measured with the timers you have available.

Given a int[] timers of the times that each of your timers can measure, you want to determine which integral intervals between 1 minute and maxInterval minutes (inclusive) cannot be measured. You always begin with all the sand in the bottom of your timers. You turn over some or all of your timers and the sand begins to fall. Whenever the sand runs out of a timer, you can again turn over some timers. You yell "Start" when you turn over some timer and "Stop" when the sand runs out of some timer. The time between the yells is the interval you are measuring. Because the king's patience is limited, you must yell "Stop" no later than maxTime minutes after turning over the first sand timer.

For example, if you had a 5-minute timer and a 7-minute timer, you could easily measure intervals of 5, 7, and 10 minutes. With a little more trouble you can measure intervals of 2, 3, 4, and 9 minutes. To measure 4 minutes, you start by flipping over both timers. When the 5-minute timer runs out, you flip it over and yell "Start", leaving the 7-minute timer running. When the 7-minute timer runs out two minutes later, you again flip over the 5-minute timer, which has been running for two minutes. The 5-minute timer runs out two minutes later, and you yell "Stop". However, no matter how you try, you cannot find a way to measure 1, 6, or 8 minutes, assuming the king's patience is limited to 10 minutes.

You will return a int[] of the intervals you cannot measure, arranged in increasing order. Note that, after years of training, you are able to turn over a sand timer instantaneously. However, tradition forbids you to ever lay a sand timer on its side.

Definition

Class:
SandTimers
Method:
badIntervals
Parameters:
int[], int, int
Returns:
int[]
Method signature:
int[] badIntervals(int[] timers, int maxInterval, int maxTime)
(be sure your method is public)

Constraints

  • timers contains between 1 and 3 elements, inclusive.
  • Each element of timers is between 1 and 20, inclusive.
  • maxInterval is between 1 and 360, inclusive.
  • maxTime is between 1 and 360, inclusive.
  • maxInterval is no greater than maxTime.

Examples

  1. { 5, 7 }

    10

    10

    Returns: {1, 6, 8 }

    The example above.

  2. { 20,20,19 }

    360

    360

    Returns: { }

  3. { 2, 10, 20 }

    30

    40

    Returns: {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29 }

    All your timers are even, so you can't measure an odd number of minutes.

  4. { 2, 5, 9 }

    360

    360

    Returns: { }

    You can measure all possible intervals.

  5. { 4 }

    23

    47

    Returns: {1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19, 21, 22, 23 }

  6. { 20, 13 }

    30

    30

    Returns: {1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 28, 29, 30 }

  7. { 20, 17, 13 }

    25

    30

    Returns: {18, 19 }

  8. {15,17,19}

    360

    360

    Returns: { }

  9. {17,19}

    1

    152

    Returns: {1 }

  10. {15,17,19}

    1

    30

    Returns: { }

  11. {15,17,19}

    1

    29

    Returns: {1 }

  12. {17,19}

    1

    153

    Returns: { }

    19*8=152 17*9=153

  13. {3,5}

    1

    6

    Returns: { }

    0 | Turn over 3 and 5 3 | 3 runs out, turn over 5 | 5 runs out, START 6 | 3 runs out, STOP

  14. {17,19}

    360

    360

    Returns: { }

  15. { 1 }

    100

    200

    Returns: { }

  16. { 2 }

    3

    16

    Returns: {1, 3 }

  17. { 15 }

    10

    95

    Returns: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

  18. { 3 }

    27

    27

    Returns: {1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26 }

  19. { 5, 5 }

    50

    60

    Returns: {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, 42, 43, 44, 46, 47, 48, 49 }

  20. { 17, 7 }

    13

    23

    Returns: {1, 2, 5, 8, 11, 12 }

  21. { 8, 3 }

    2

    32

    Returns: { }

  22. { 13, 6 }

    48

    50

    Returns: { }

  23. { 10, 20 }

    4

    38

    Returns: {1, 2, 3, 4 }

  24. { 2, 17 }

    7

    46

    Returns: { }

  25. { 11, 8 }

    8

    16

    Returns: {1, 2, 4, 7 }

  26. { 7, 2 }

    42

    44

    Returns: { }

  27. { 15, 11 }

    27

    49

    Returns: {10 }

  28. { 11, 11 }

    1

    18

    Returns: {1 }

  29. { 8, 2 }

    36

    38

    Returns: {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35 }

  30. { 7, 15 }

    25

    49

    Returns: { }

  31. { 3, 10 }

    32

    47

    Returns: { }

  32. { 9, 17 }

    15

    17

    Returns: {1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15 }

  33. { 1, 9 }

    11

    32

    Returns: { }

  34. { 1, 12 }

    31

    46

    Returns: { }

  35. { 3, 19 }

    26

    34

    Returns: { }

  36. { 18, 10 }

    12

    41

    Returns: {1, 3, 5, 7, 9, 11 }

  37. { 8, 16 }

    43

    44

    Returns: {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43 }

  38. { 12, 5 }

    47

    48

    Returns: { }

  39. { 6, 9 }

    10

    42

    Returns: {1, 2, 4, 5, 7, 8, 10 }

  40. { 7, 3 }

    18

    321

    Returns: { }

  41. { 15, 6 }

    314

    323

    Returns: {1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86, 88, 89, 91, 92, 94, 95, 97, 98, 100, 101, 103, 104, 106, 107, 109, 110, 112, 113, 115, 116, 118, 119, 121, 122, 124, 125, 127, 128, 130, 131, 133, 134, 136, 137, 139, 140, 142, 143, 145, 146, 148, 149, 151, 152, 154, 155, 157, 158, 160, 161, 163, 164, 166, 167, 169, 170, 172, 173, 175, 176, 178, 179, 181, 182, 184, 185, 187, 188, 190, 191, 193, 194, 196, 197, 199, 200, 202, 203, 205, 206, 208, 209, 211, 212, 214, 215, 217, 218, 220, 221, 223, 224, 226, 227, 229, 230, 232, 233, 235, 236, 238, 239, 241, 242, 244, 245, 247, 248, 250, 251, 253, 254, 256, 257, 259, 260, 262, 263, 265, 266, 268, 269, 271, 272, 274, 275, 277, 278, 280, 281, 283, 284, 286, 287, 289, 290, 292, 293, 295, 296, 298, 299, 301, 302, 304, 305, 307, 308, 310, 311, 313, 314 }

  42. { 19, 9 }

    23

    108

    Returns: { }

  43. { 6, 18 }

    266

    300

    Returns: {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 91, 92, 93, 94, 95, 97, 98, 99, 100, 101, 103, 104, 105, 106, 107, 109, 110, 111, 112, 113, 115, 116, 117, 118, 119, 121, 122, 123, 124, 125, 127, 128, 129, 130, 131, 133, 134, 135, 136, 137, 139, 140, 141, 142, 143, 145, 146, 147, 148, 149, 151, 152, 153, 154, 155, 157, 158, 159, 160, 161, 163, 164, 165, 166, 167, 169, 170, 171, 172, 173, 175, 176, 177, 178, 179, 181, 182, 183, 184, 185, 187, 188, 189, 190, 191, 193, 194, 195, 196, 197, 199, 200, 201, 202, 203, 205, 206, 207, 208, 209, 211, 212, 213, 214, 215, 217, 218, 219, 220, 221, 223, 224, 225, 226, 227, 229, 230, 231, 232, 233, 235, 236, 237, 238, 239, 241, 242, 243, 244, 245, 247, 248, 249, 250, 251, 253, 254, 255, 256, 257, 259, 260, 261, 262, 263, 265, 266 }

  44. { 6, 10 }

    112

    292

    Returns: {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111 }

  45. { 6, 4 }

    94

    210

    Returns: {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93 }

  46. { 17, 19 }

    120

    260

    Returns: { }

  47. { 18, 9 }

    27

    189

    Returns: {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26 }

  48. { 1, 12 }

    274

    297

    Returns: { }

  49. { 9, 13 }

    325

    342

    Returns: { }

  50. { 20, 20 }

    360

    360

    Returns: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359 }

  51. { 14, 3, 1 }

    10

    16

    Returns: { }

  52. { 10, 19, 3 }

    4

    10

    Returns: {2 }

  53. { 16, 7, 4 }

    8

    22

    Returns: { }

  54. { 4, 15, 13 }

    5

    9

    Returns: {1, 2, 3, 5 }

  55. { 3, 8, 18 }

    24

    27

    Returns: { }

  56. { 8, 9, 16 }

    7

    20

    Returns: { }

  57. { 7, 4, 14 }

    12

    36

    Returns: { }

  58. { 12, 18, 8 }

    31

    32

    Returns: {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31 }

  59. { 19, 9, 19 }

    23

    39

    Returns: { }

  60. { 6, 9, 8 }

    15

    20

    Returns: { }

  61. { 20, 9, 7 }

    20

    31

    Returns: { }

  62. { 7, 6, 17 }

    1

    30

    Returns: { }

  63. { 10, 8, 1 }

    304

    346

    Returns: { }

  64. { 10, 10, 14 }

    265

    266

    Returns: {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209, 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239, 241, 243, 245, 247, 249, 251, 253, 255, 257, 259, 261, 263, 265 }

  65. { 12, 6, 10 }

    195

    357

    Returns: {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 181, 183, 185, 187, 189, 191, 193, 195 }

  66. { 16, 11, 12 }

    67

    117

    Returns: { }

  67. { 2, 1, 9 }

    243

    277

    Returns: { }

  68. { 15, 6, 13 }

    170

    295

    Returns: { }

  69. { 2, 5, 14 }

    104

    151

    Returns: { }

  70. { 2, 20, 10 }

    350

    355

    Returns: {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209, 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239, 241, 243, 245, 247, 249, 251, 253, 255, 257, 259, 261, 263, 265, 267, 269, 271, 273, 275, 277, 279, 281, 283, 285, 287, 289, 291, 293, 295, 297, 299, 301, 303, 305, 307, 309, 311, 313, 315, 317, 319, 321, 323, 325, 327, 329, 331, 333, 335, 337, 339, 341, 343, 345, 347, 349 }

  71. {20, 13 }

    30

    30

    Returns: {1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 28, 29, 30 }

  72. {6, 14, 15 }

    360

    360

    Returns: { }

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: