TopCoder Statistics - Problem Statement

Problem Statement

A city is square and is laid out in nice regular blocks, except that there is one block that has a "shortcut", a narrow road that goes diagonally through the block. The bank has just been robbed, and our one on-duty police car starts to chase down the robbers. The police and robbers always drive at top speed, and they have exactly the same top speed. Neither the police nor the robbers can leave the city.

It takes 10 seconds to drive one block. It also takes 10 seconds to drive the shortcut. The police have one advantage -- they have a "bug" in the robbers' car. One of the robbers tells the driver which way to turn just before they reach each intersection, so the police can choose their next turn appropriately. The robbers are apprehended when the police and robbers are at the same intersection at the same time or when a head-on collision occurs on the shortcut. (The regular roads are divided roads, so the police cannot apprehend the robbers if they pass each other going in opposite directions.) U-turns at intersections are possible, but neither the police nor the robbers may slow down or stop.

Create a class Robbery that contains the method apprehend that takes the width of the city, n, and a int[] map, giving the locations of the shortcut, robbers and police as inputs and returns the amount of time until the robbers are apprehended. If the police can never apprehend the robbers, the method should return -1. Assume that both the police and robbers behave optimally (other than robbing the bank in the first place).

n is the number of blocks in both directions (since the city is square). The intersections are located at x,y where x and y are between 0 and n inclusive. map contains exactly 8 values: shortcutX1,shortcutY1,shortcutX2,shortcutY2, policeX,policeY,robbersX,robbersY.

Definition

Class:: Robbery
Method:: apprehend
Parameters:: int, int[]
Returns:: int
Method signature:: int apprehend(int n, int[] map)
(be sure your method is public)

Constraints

n is between 2 and 30 inclusive.
map contains exactly 8 elements.
Each element in map is between 0 and n inclusive.
The absolute value of (shortcutX1 - shortcutX2) is 1.
The absolute value of (shortcutY1 - shortcutY2) is 1.
map specifies distinct locations for the police and robbers.

Examples

3

{0,1,1,2,1,1,3,1}

Returns: 30

*---*---*---* | | | | *---*---*---* | / | | | *---P---*---R | | | | *---*---*---* (All example diagrams have (0,0) in the lower left corner.) If the robbers go west, the police will go east apprehending in 1*10 seconds. If the robbers go south, the police will go east. Then the robbers will have to go north or west and will be apprehended after 2*10 = 20 seconds. If the robbers go north, they will be trapped when they get to the northeast corner of the city, and will be apprehended after 30 seconds.
3

{0,1,1,2,1,1,2,1}

Returns: 50

*---*---*---* | | | | *---*---*---* | / | | | *---P---R---* | | | | *---*---*---* The best strategy for the police is to go west, then northeast (using the shortcut). The robbers can do no better than to head north, then east, then south and south. Even so, they will then be trapped in the southeast corner of the city and will be apprehended 10 seconds later.
5

{1,1,2,2,3,3,4,4}

Returns: 30
5

{1,1,2,2,4,4,3,3}

Returns: 120
5

{2,2,1,1,4,4,3,3}

Returns: 120
5

{1,1,2,2,3,2,3,3}

Returns: 90
5

{4,2,5,1,4,1,4,0}

Returns: 70
5

{4,4,5,5,5,3,4,4}

Returns: 70

*---*---*---*---*---* | | | | | / | *---*---*---*---R---* | | | | | | *---*---*---*---*---P | | | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---*
5

{5,5,4,4,5,4,5,5}

Returns: 60

*---*---*---*---*---R | | | | | / | *---*---*---*---*---P | | | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---*
3

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

Returns: 50

*---*---*---* | | | | *---R---P---* | | \ | | *---*---*---* | | | | *---*---*---*
3

{1,0,0,1,3,0,1,0}

Returns: 70

*---*---*---* | | | | *---*---*---* | | | | *---*---*---* | \ | | | *---R---*---P
3

{1,3,0,2,0,0,1,3}

Returns: 70

*---R---*---* | / | | | *---*---*---* | | | | *---*---*---* | | | | P---*---*---*
3

{2,2,1,1,2,1,3,3}

Returns: 40

*---*---*---R | | | | *---*---*---* | | / | | *---*---P---* | | | | *---*---*---*
5

{1,3,2,2,1,2,0,2}

Returns: 60

*---*---*---*---*---* | | | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---* | | \ | | | | R---P---*---*---*---* | | | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---*
5

{2,2,3,1,2,1,2,0}

Returns: 60
3

{1,2,0,1,2,2,1,1}

Returns: 30

*---*---*---* | | | | *---*---P---* | / | | | *---R---*---* | | | | *---*---*---*
3

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

Returns: 40

*---*---*---* | | | | *---P---R---* | | \ | | *---*---*---* | | | | *---*---*---*
5

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

Returns: 90

P---*---*---*---*---* | | | | | | R---*---*---*---*---* | | \ | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---*
2

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

Returns: 10
3

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

Returns: 50
10

{8,2,9,1,3,7,2,7}

Returns: 280
10

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

Returns: 160
4

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

Returns: 120
20

{1,2,0,3,2,0,2,1}

Returns: 400

*---*---*---* | \ | | | *---*---*---* | | | | *---*---R---* | | | | *---*---P---*
20

{0,1,1,0,20,20,19,20}

Returns: 780
30

{0,1,1,0,30,30,30,29}

Returns: 1180
30

{20,20,21,21,10,10,30,30}

Returns: 620

Statistics

Problem Statement for "Robbery"

Problem Statement

Definition

Constraints

Examples