StreetWalking
SRM 395 · 2008-03-26 · by connect4
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.
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.
4 2 3 10 Returns: 18
The fastest way to your home is to not sneak at all.
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 0 12 10 Returns: 20
One possible path is (0,0)->(1,1)->(2,0).
1000000 1000000 1000 1000 Returns: 1000000000
Formerly the maximal return
0 0 12 25 Returns: 0
Minimal return
1000000000 1000000000 10000 10000 Returns: 10000000000000
New maximum return.
123 456 78 90 Returns: 37044
The numbers look cool here :)
Submissions are judged against all 91 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StreetWalking with a public method long long minTime(int X, int Y, int walkTime, int sneakTime) · 91 test cases · 2 s / 256 MB per case