Statistics

Problem Statement for "Turnpike"

Problem Statement

The turnpike has mile markers at each mile along its length, with 0 at the western end and pikeLength at the eastern end (so it is exactly pikeLength miles long). We locate our service plazas at various mile markers. Each plaza can service traffic going in either direction, so we never place multiple plazas at the same mile marker. We also never place a plaza at either end of the turnpike.

The locations of all the existing plazas are given in a int[] plazas. We are interested in locating n new plazas along the turnpike in such a way as to minimize the longest segment of turnpike that has no plaza. Given pikeLength, n, and plazas, determine the best locations for the n new plazas and return the length of the longest unserviced segment after the new plazas have been added.

Definition

Class:
Turnpike
Method:
unserviced
Parameters:
int, int, int[]
Returns:
int
Method signature:
int unserviced(int pikeLength, int n, int[] plazas)
(be sure your method is public)

Constraints

  • pikeLength will be between 100 and 1000, inclusive.
  • n will be between 1 and 100, inclusive.
  • plazas will contain between 0 and 50 elements, inclusive.
  • The elements in plazas will be distinct values between 1 and pikeLength-1, inclusive.
  • n plus the number of elements in plazas will be less than pikeLength.

Examples

  1. 1000

    1

    {300,701,800}

    Returns: 300

    The new plaza should be placed in the segment between 300 and 701. But the best we can do is to make the longest unserviced segment be of length 300, since the segment from 0 to 300 will still be unserviced.

  2. 1000

    1

    {200,701,800}

    Returns: 251

    We should place the new plaza in the segment between 200 and 701. We can reduce the longest unserviced segment to 251 by placing it either at 450 or at 451.

  3. 800

    7

    {622,411,201,555,755,82}

    Returns: 70

    The seven new plazas can be distributed along the turnpike so that the longest unserviced segments are from 201 to a new plaza at 271, from 271 to 341 (also a new plaza), and from 341 to the existing plaza at 411.

  4. 700

    2

    {200,400,600}

    Returns: 200

  5. 700

    3

    {200,400,600}

    Returns: 100

    //int k=699, n=4; int[] p = {200,400,600}; //698 //int k=699, n=4; int[] p = {200,400,600,698}; //697 //int k=699, n=4; int[] p = {200,401,600,698}; //501 //int k=720, n=5; int[] p = {200,401,600,708}; //700 //int k=720, n=5; int[] p = {200,401,600}; //700 //int k=100, n=49; int[] p = {2,4,6,8,10,13,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,99};

  6. 601

    3

    {}

    Returns: 151

  7. 666

    5

    {}

    Returns: 111

  8. 147

    96

    {107, 113, 67, 104, 111, 24, 8, 89, 102, 17, 21, 48, 128, 63, 12, 80, 15, 52, 7, 4, 108, 120, 82, 2, 22, 137, 37, 109, 110, 18, 30, 115, 119, 78, 103, 126, 55, 23, 84, 85, 5, 13, 95, 56, 146, 65, 134, 72, 3, 112}

    Returns: 1

  9. 134

    93

    {13, 11, 35, 119, 10, 113, 41, 112, 15, 14, 65, 97, 44, 106, 88, 69, 16, 116, 109, 89, 98, 120, 70, 54, 111, 129, 105, 12, 108, 24, 62, 86, 32, 126, 56, 81, 103, 91, 1, 50}

    Returns: 1

  10. 128

    33

    {30, 124, 80, 34, 71, 6, 82, 114, 112, 8, 31, 60, 79, 24, 51, 97, 103, 117, 57, 13, 90, 45, 36, 3, 109, 122, 42, 89, 43}

    Returns: 3

  11. 731

    46

    {536, 49, 558, 506}

    Returns: 15

  12. 385

    89

    {213, 235, 373, 252, 109, 364, 288, 358, 87, 246, 69, 161, 351}

    Returns: 4

  13. 450

    67

    {134, 328, 367, 103, 216, 104, 12, 394, 211, 197, 285, 87, 151, 277, 269, 178, 100, 276, 166, 370, 441, 243, 54, 43, 14, 66, 358, 60, 37, 272, 395, 385, 88, 415, 106, 313, 375}

    Returns: 6

  14. 916

    9

    {205, 619, 643, 780, 505, 297, 538, 227, 817, 325, 88, 833, 402, 21, 191, 46, 314, 724, 454, 591, 687, 111, 357, 44, 195, 494, 504, 98, 776, 681, 701, 834}

    Returns: 40

  15. 440

    69

    {365, 202, 244, 416, 99, 417, 438, 1, 237, 94, 73, 209, 431, 2, 107, 149, 349, 395, 30, 143, 62, 160, 317, 21, 169, 415, 140, 367, 67, 247, 411, 396, 206, 268, 40, 47, 300, 84, 83, 427, 91, 138, 361, 170, 26}

    Returns: 5

  16. 668

    32

    {60, 279, 119, 499, 407, 118, 138, 262, 384, 277, 425, 607, 610, 367, 470, 321, 374, 380, 255, 547, 343, 84, 158, 300, 544, 382, 312, 538, 438, 551, 549, 436, 518, 381, 612, 410, 627, 266, 289, 299}

    Returns: 14

  17. 420

    26

    {357, 28, 347, 309, 138, 376, 239, 159, 300, 64, 205, 136, 2, 227, 93, 221, 112, 37, 18, 415, 220, 384, 120, 115, 168, 1, 134}

    Returns: 11

  18. 606

    56

    {501, 157, 407, 186, 399, 140, 145, 494, 422, 71, 391, 536, 297, 300}

    Returns: 10

  19. 628

    68

    {191, 251, 536, 277, 290, 13, 548, 503, 331, 154, 344, 369, 545, 625, 136, 279, 236, 248, 353, 176, 307, 53, 384, 213, 223, 441, 49, 263, 401}

    Returns: 8

  20. 123

    82

    {23, 19, 86, 39, 33, 17, 47, 70, 43, 14, 111, 9, 7, 66, 38}

    Returns: 2

  21. 503

    63

    {433, 152, 53, 211, 79, 261, 406, 124, 196, 495, 326, 347, 323, 18, 42, 330, 453, 381, 248, 397, 414, 151, 349, 129, 403, 370}

    Returns: 7

  22. 433

    63

    {366, 98, 258, 136, 185, 227, 362, 352, 237, 424, 224, 347, 327, 416, 401, 285, 279, 80, 20, 278, 296, 24, 332, 144, 10, 384, 333, 65, 305, 420, 124, 221, 182, 169, 127, 428, 75, 187, 84, 19, 76, 388, 174, 242, 241, 11}

    Returns: 5

  23. 778

    38

    {389, 414, 186, 83}

    Returns: 20

  24. 386

    47

    {224, 285, 315, 107, 234, 287, 243, 204, 73, 291, 32, 66, 19, 62, 140, 10, 63, 68, 322, 211, 72, 83, 300, 236, 292, 194, 161, 40, 104, 215, 39, 355, 295, 340, 130, 316, 346, 110}

    Returns: 6

  25. 452

    19

    {293, 391, 167, 93, 95, 313, 282, 8, 65, 17, 323, 163, 173}

    Returns: 17

  26. 695

    28

    {3, 307, 199, 392, 111, 418, 371, 596, 374, 308, 253, 177, 630, 294, 110, 650, 208, 448, 449, 672, 36, 166, 366, 189, 173, 547, 321, 60, 483, 601, 427, 654, 586, 568, 655, 390, 220, 605, 521, 267, 628, 254, 406}

    Returns: 14

  27. 576

    55

    {180, 272, 302, 82, 261, 541, 373, 265, 143, 92, 144, 16, 505, 504, 551, 26, 123}

    Returns: 9

  28. 230

    74

    {136, 40, 72, 55, 153, 108, 71, 83, 90, 140, 141, 103, 37, 176, 46, 63, 31, 116, 161, 82, 36, 78, 174, 129, 109, 151, 147, 92, 204, 180, 41, 173, 114, 127, 22, 91, 89, 84, 171, 156}

    Returns: 3

  29. 502

    40

    {240, 284, 168, 174, 51, 371, 420, 124, 247, 318, 409, 91, 374, 163, 292, 459, 131}

    Returns: 11

  30. 433

    17

    {7, 173, 190, 94}

    Returns: 22

  31. 583

    95

    {}

    Returns: 7

  32. 524

    38

    {463, 452, 179, 200, 84, 192, 317, 138, 407, 225, 75, 24, 203, 446, 91, 404, 361, 380, 144, 36, 376, 245, 386, 430}

    Returns: 11

  33. 347

    41

    {320, 208, 271, 306, 137, 20, 148, 170, 259, 329, 283, 282, 183, 122, 57, 143, 214, 70, 6, 142, 255, 52, 281, 190, 166, 107, 85, 14, 159, 231, 132, 261, 252, 302, 173, 215}

    Returns: 6

  34. 674

    10

    {406, 174, 267, 273, 93, 183, 364, 178, 547, 5, 519}

    Returns: 43

  35. 1000

    100

    {701, 878, 844, 88, 659, 67, 794, 821, 627, 135, 390, 72, 733, 56, 749, 773, 856, 873, 570, 980, 440, 365, 577, 156, 447, 160, 963, 863, 767, 815, 506, 377, 695, 580, 857, 881, 346, 382, 367, 279, 40, 507, 652, 635, 232, 341, 285, 111, 28, 293}

    Returns: 8

  36. 1000

    100

    {280, 306, 830, 87, 582, 100, 163, 954, 882, 828, 778, 9, 345, 756, 526, 576, 516, 706, 630, 535, 567, 490, 224, 396, 28, 761, 964, 316, 989, 789, 271, 482, 313, 825, 740, 240, 542, 926, 236, 398, 38, 967, 551, 500, 950, 903, 568, 109, 940, 376}

    Returns: 8

  37. 1000

    100

    {575, 897, 427, 182, 476, 995, 212, 932, 758, 801, 663, 798, 647, 69, 694, 639, 169, 516, 773, 802, 699, 954, 745, 176, 463, 375, 188, 47, 714, 905, 15, 299, 436, 224, 439, 623, 385, 599, 881, 26, 49, 22, 70, 754, 657, 338, 328, 137, 109, 902}

    Returns: 8

  38. 1000

    100

    {219, 863, 512, 935, 803, 175, 22, 801, 629, 832, 956, 913, 196, 627, 461, 306, 911, 708, 362, 143, 332, 334, 818, 440, 684, 351, 549, 918, 134, 202, 404, 30, 838, 9, 892, 831, 21, 210, 788, 693, 260, 639, 945, 110, 743, 896, 697, 843, 379, 738}

    Returns: 8

  39. 1000

    100

    {431, 112, 614, 934, 682, 726, 256, 429, 227, 693, 697, 464, 469, 114, 999, 229, 495, 55, 509, 845, 711, 62, 85, 990, 873, 539, 411, 947, 353, 372, 484, 460, 265, 334, 986, 201, 264, 738, 390, 93, 401, 280, 952, 482, 11, 755, 82, 20, 157, 371}

    Returns: 9

  40. 1000

    100

    {81, 168, 366, 17, 663, 535, 863, 568, 995, 512, 118, 990, 817, 978, 745, 494, 365, 489, 437, 547, 748, 480, 957, 60, 316, 279, 804, 443, 222, 236, 41, 187, 970, 772, 102, 416, 779, 539, 227, 862, 689, 100, 711, 359, 654, 721, 250, 753, 325, 461}

    Returns: 8

  41. 1000

    100

    {907, 344, 527, 962, 851, 468, 748, 994, 858, 442, 625, 431, 768, 802, 347, 911, 961, 372, 871, 972, 368, 322, 774, 23, 219, 577, 683, 450, 363, 84, 735, 892, 899, 833, 422, 346, 175, 173, 323, 487, 337, 398, 702, 542, 786, 738, 553, 531, 852, 145}

    Returns: 8

  42. 1000

    100

    {979, 542, 261, 778, 839, 578, 571, 697, 286, 49, 248, 330, 630, 775, 791, 189, 962, 337, 140, 291, 849, 123, 196, 480, 524, 445, 325, 282, 651, 389, 34, 132, 195, 254, 951, 783, 395, 522, 23, 490, 481, 46, 990, 903, 978, 181, 948, 628, 925, 669}

    Returns: 8

  43. 1000

    100

    {498, 943, 76, 887, 802, 849, 837, 13, 727, 751, 587, 648, 787, 460, 934, 748, 819, 226, 105, 600, 85, 716, 454, 844, 425, 384, 264, 840, 632, 69, 546, 609, 975, 525, 252, 923, 328, 852, 97, 269, 220, 697, 367, 371, 731, 578, 756, 710, 141, 408}

    Returns: 8

  44. 1000

    100

    {9, 170, 921, 259, 146, 394, 274, 110, 345, 863, 121, 512, 158, 851, 509, 369, 181, 114, 191, 885, 305, 949, 85, 624, 927, 285, 617, 912, 395, 542, 168, 906, 620, 23, 289, 786, 681, 745, 571, 297, 677, 213, 60, 610, 313, 765, 800, 856, 958, 319}

    Returns: 8

  45. 1000

    41

    {622, 411, 201, 555, 755, 82, 1, 32, 55, 999, 123, 112 }

    Returns: 23

  46. 100

    1

    { }

    Returns: 50

  47. 100

    2

    { }

    Returns: 34

  48. 1000

    100

    {10, 30, 50, 70, 90, 110, 130, 150, 170, 190, 210, 230, 250, 270, 290, 310, 330, 350, 370, 390, 410, 430, 450, 470, 490, 510, 530, 550, 570, 590, 610, 630, 650, 670, 690, 710, 730, 750, 770, 790, 810, 830, 850, 870, 890, 910, 930, 950, 970, 990 }

    Returns: 7

  49. 1000

    2

    { }

    Returns: 334

  50. 100

    99

    { }

    Returns: 1

  51. 100

    47

    { }

    Returns: 3

  52. 999

    99

    {1, 2, 4, 8, 16, 32, 64, 128, 256, 512 }

    Returns: 10

  53. 101

    99

    { }

    Returns: 2

  54. 1000

    3

    { }

    Returns: 250

  55. 1000

    1

    { }

    Returns: 500

  56. 800

    1

    { }

    Returns: 400

  57. 1000

    100

    {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100 }

    Returns: 9

  58. 1000

    50

    {20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300, 320, 340, 360, 380, 400, 420, 440, 460 }

    Returns: 20

  59. 102

    49

    {47, 31, 30, 53, 4, 88, 69, 29, 5 }

    Returns: 2

  60. 100

    2

    {20 }

    Returns: 27

  61. 100

    5

    { }

    Returns: 17

  62. 1000

    100

    { }

    Returns: 10

  63. 149

    41

    {109, 142, 34, 13, 76, 39, 138, 112, 22, 20, 5 }

    Returns: 4

  64. 1000

    5

    { }

    Returns: 167

  65. 298

    2

    { }

    Returns: 100

  66. 214

    25

    {64, 59, 56, 58, 174, 34, 162, 74, 130, 187, 3, 212, 25, 194, 170, 166, 38, 93, 86 }

    Returns: 6

  67. 100

    2

    {48, 52 }

    Returns: 24

  68. 1000

    1

    {200 }

    Returns: 400

  69. 100

    98

    {1 }

    Returns: 1

  70. 1000

    30

    { }

    Returns: 33

  71. 1000

    50

    {402, 294, 763, 516, 230, 48, 528, 944, 562, 857, 681, 859, 952, 319, 607, 713, 993, 566, 235, 288, 222, 90, 216, 9, 616, 87, 301, 19, 160, 638, 240, 986, 331, 78, 470, 237, 16, 467, 95, 327, 999, 905, 575, 997, 954, 930, 141, 637, 238, 369 }

    Returns: 15

  72. 400

    1

    {5, 10 }

    Returns: 195

  73. 988

    32

    {940, 457, 198, 771, 159, 961, 112, 418 }

    Returns: 27

  74. 1000

    17

    {622, 411, 201, 555, 755, 82, 800, 850, 910, 830, 950, 500, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155 }

    Returns: 42

  75. 1000

    97

    { }

    Returns: 11

  76. 100

    4

    {50 }

    Returns: 17

  77. 951

    19

    {50, 100, 150, 200, 250, 300, 350, 400, 450, 500, 550, 600, 650, 700, 750, 800, 850, 900 }

    Returns: 26

  78. 1000

    41

    { }

    Returns: 24

  79. 800

    2

    { }

    Returns: 267

  80. 201

    3

    {100 }

    Returns: 50

  81. 1000

    100

    {20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300, 320, 340, 360, 380, 400, 420, 440, 460, 480, 500, 520, 540, 560, 580, 600, 620, 640, 660, 680, 700, 720, 740, 760, 780, 800, 820, 900, 950 }

    Returns: 9

  82. 130

    1

    { }

    Returns: 65

  83. 128

    2

    { }

    Returns: 43

  84. 500

    7

    { }

    Returns: 63

  85. 100

    98

    {50 }

    Returns: 1

  86. 100

    2

    {34, 35 }

    Returns: 33

  87. 1000

    100

    {321, 444, 876 }

    Returns: 10

  88. 1000

    99

    {1, 101, 123, 44, 666, 999, 333, 222, 555, 766 }

    Returns: 10

  89. 1000

    11

    { }

    Returns: 84

  90. 100

    3

    { }

    Returns: 25

  91. 100

    2

    {51 }

    Returns: 26

  92. 121

    3

    {60 }

    Returns: 30

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: