Connection Status:
Competition Arena > Turnpike

Turnpike

TCO07 Round 1A · 2007-03-07 · by dgoodman

TCO07 Round 1A · 2007-03-07 · by dgoodman · Search
Class Name: Turnpike
Return Type: int
Method Name: unserviced
Arg Types: (int, int, vector<int>)
Problem Statement

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.

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

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

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

3)
700
2
{200,400,600}
Returns: 200
4)
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};

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

Coding Area

Language: C++17 · define a public class Turnpike with a public method int unserviced(int pikeLength, int n, vector<int> plazas) · 92 test cases · 2 s / 256 MB per case

Submitting as anonymous