TopCoder problem "StreetWalking" used in SRM 395 (Division I Level One , Division II Level Two)



Problem Statement

    

You are walking home from school through the city. The city is infinite in size, with vertical streets located at every integer X value and horizontal streets located at every Y value. You are currently located at (0,0) and are trying to get to your home, located at (X, Y). You have two methods of travel available to you: you can walk along the street to proceed to a horizontally or vertically adjacent intersection (which takes walkTime seconds), or you can sneak across the block diagonally to the opposite corner (taking sneakTime seconds). You can walk or sneak in any of the eight directions shown in the image (see example 2).





Return the least amount of time that it will take you to return home. See the examples for clarification.

 

Definition

    
Class:StreetWalking
Method:minTime
Parameters:int, int, int, int
Returns:long
Method signature:long minTime(int X, int Y, int walkTime, int sneakTime)
(be sure your method is public)
    
 

Constraints

-X will be between 0 and 1,000,000,000, inclusive.
-Y will be between 0 and 1,000,000,000, inclusive.
-walkTime will be between 1 and 10000, inclusive.
-sneakTime will be between 1 and 10000, inclusive.
 

Examples

0)
    
4
2
3
10
Returns: 18
The fastest way to your home is to not sneak at all.
1)
    
4
2
3
5
Returns: 16
In this case, it is faster to sneak across twice, following the path (0,0)->(1,0)->(2,1)->(3,1)->(4,2). This takes 10 seconds for the sneaking, and 6 seconds for the walking.
2)
    
2
0
12
10
Returns: 20
One possible path is (0,0)->(1,1)->(2,0).
3)
    
25
18
7
11
Returns: 247
4)
    
24
16
12
10
Returns: 240
5)
    
10000000
50000000
800
901
Returns: 41010000000
6)
    
135
122
43
29
Returns: 3929

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8464

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11129&pm=8464

Writer:

connect4

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Greedy, Simple Math