JOIN
Get Time

   Problem Statement  

 Problem Statement for LongMansionDiv1

Problem Statement

    

LYC is the pet dog of Emperor Zhangzj of Yali Empire. Zhangzj has a huge affluence. Besides his palace, he has multiple estates. One of them is the Long Mansion, a famous site in Yali. LYC loves to play. One day, he accidentally enters the labyrinthine Long Mansion.

The mansion can be seen as a grid of unit square cells. There are N rows, indexed from 0 to (N - 1). The number of columns is infinite in one direction. The columns are indexed by nonnegative integers, starting from 0. You are given ints sX, sY, eX, eY. Initially LYC is standing on the cell on the sXth row, and the sYth column. The exit is at the cell on the eXth row, and the eYth column. LYC can walk to a cell that shares an edge with the cell he is at. He wished to reach the exit as soon as possible.

Unfortunately, each cell contains some obstacles that slow LYC down. For each cell we know the time LYC needs to spend there while passing through the cell. LYC also needs to spend that amount of time in the initial cell and in the exit cell as well. There is a pattern to the obstacles: each column of the mansion looks the same. In other words, all cells within any given row contain the same obstacle type, and therefore they delay LYC by the same amount of time. For example, the entire first row are some bushes, the entire second row contains some walls, and so on. You are given the times in the int[] t. More precisely, LYC will spend t[i] time in each cell he visits in row i.

You are given one int[] t and 4 ints sX, sY, eX, eY. Return the minimal time LYC needs to spend to reach the exit.

 

Definition

    
Class:LongMansionDiv1
Method:minimalTime
Parameters:int[], int, int, int, int
Returns:long
Method signature:long minimalTime(int[] t, int sX, int sY, int eX, int eY)
(be sure your method is public)
    
 

Constraints

-

N will be between 1 and 50, inclusive.

-

t will contain exactly N elements.

-

Each element of t will be between 1 and 1,000, inclusive.

-

sX and eX will be between 0 and (N - 1), inclusive.

-

sY and eY will be between 0 and 1,000,000,000 inclusive.

 

Examples

0)
    
{5, 3, 10}
2
0
2
2
Returns: 29

The optimal path would be (2, 0) &rarr (1, 0) &rarr (1, 1) &rarr (1, 2) &rarr (2, 2). The total time would be 10 + 3 + 3 + 3 + 10 = 29. Note that you should count the time LYC spends on the inital cell and the cell of the exit as well.

1)
    
{5, 3, 10}
0
2
0
0
Returns: 15

This time the optimal path would be (0, 2) &rarr (0, 1) &rarr (0, 0).

2)
    
{137, 200, 184, 243, 252, 113, 162}
0
2
4
2
Returns: 1016
3)
    
{995, 996, 1000, 997, 999, 1000, 997, 996, 1000, 996, 1000, 997, 999, 996, 1000, 998, 999, 995, 995, 998, 995, 998, 995, 997, 998, 996, 998, 996, 997, 1000, 998, 997, 995, 1000, 996, 997, 1000, 997, 997, 999, 998, 995, 999, 999, 1000, 1000, 998, 997, 995, 999}
18
433156521
28
138238863
Returns: 293443080673
4)
    
{1}
0
0
0
0
Returns: 1

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 719 Round 1 - Division I, Level One