TopCoder Statistics - Problem Statement

Problem Statement

Our warehouse is square, 200 feet on each side, with solid north and south walls. The east and west walls have sliding doors which allow trucks free entry and exit. Trucks come in a variety of sizes, but the width of each truck is an integer number of feet. Unfortunately the roof is supported by posts (of negligible size).

We want to drive big trucks in a straight line into the warehouse through the west wall and (after unloading and without changing direction) out through the east wall. Create a class Warehouse that contains the method feetWide that takes the positions of the posts as inputs and returns the width of the widest truck (of integral width) that can drive straight through without touching any posts (or the north or south wall). The positions of the posts are given by int[] x and int[] y: the i-th element of x and y gives the distance in feet east and north respectively from the southwest corner of the building to the i-th post.

Definition

Class:: Warehouse
Method:: feetWide
Parameters:: int[], int[]
Returns:: int
Method signature:: int feetWide(int[] x, int[] y)
(be sure your method is public)

Constraints

x has between 1 and 50 elements inclusive
y has the same number of elements as x
each element of x and y is between 0 and 200 inclusive

Examples

{0}

{200}

Returns: 199

The only post is at one of the corners of the building.
{100,100,120}

{60,140,180}

Returns: 79

The best path is due east, but the first and second posts are only 80 feet apart so the truck must be less than 80 feet wide.
{100,120}

{60,140}

Returns: 82

The best path is a little south of east, going between the two posts. The distance between the posts is sqrt(6800) = 82.xxx
{40,80,120}

{80,40,160}

Returns: 101
{0,0,100}

{50,100,150}

Returns: 89
{100,0}

{100,2}

Returns: 99
{0,200,200,199,100}

{195,100,50,195,173}

Returns: 92
{170,170,171}

{150,100,50}

Returns: 50
{170,170,140}

{150,100,50}

Returns: 58
{170,170,200}

{150,100,50}

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

{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,50,48,46,44,42,40,38,36,34,32,30,28,26,24,22,20,18,16,14,12,10,8,6,4,2}

Returns: 149
{40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40}

{70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70}

Returns: 129
{0,21,0,0,0,0,0}

{49,21,170,140,110,80,60}

Returns: 34
{0,22,0,0,0,0,0}

{49,21,170,140,110,80,60}

Returns: 35
{0,21,0,0,0,0,0}

{59,31,170,140,110,80,60}

Returns: 34
{0,21,0,0,0,0,0,200,200,200}

{49,21,170,140,110,80,60,170,140,110}

Returns: 32
{ 175, 60, 27, 50, 65, 87, 194, 5, 173, 93, 152, 103, 60, 132, 27, 60, 140, 171, 177, 161, 99, 97, 73, 177, 200, 6, 58, 173, 190, 111, 119, 104, 31, 164, 107, 43, 62, 3, 170, 183, 104, 45, 12, 70, 150, 67, 43, 68, 69, 39 }

{ 176, 156, 114, 47, 96, 85, 184, 52, 196, 4, 41, 150, 108, 186, 184, 90, 172, 43, 79, 160, 187, 31, 1, 31, 114, 89, 195, 56, 192, 150, 110, 18, 168, 8, 129, 167, 115, 169, 112, 78, 103, 120, 97, 18, 86, 102, 146, 174, 107, 118 }

Returns: 22
{ 0, 200 }

{ 5, 195 }

Returns: 194
{ 0, 50, 50 }

{ 190, 191, 5 }

Returns: 185
{ 100, 100, 160 }

{ 40, 160, 140 }

Returns: 113
{ 10, 20, 30, 40, 50, 60, 70, 130, 140, 150, 160, 170, 180, 190 }

{ 10, 20, 30, 40, 50, 60, 70, 130, 140, 150, 160, 170, 180, 190 }

Returns: 81

Statistics

Problem Statement for "Warehouse"

Problem Statement

Definition

Constraints

Examples