Teleportation
InterviewTime limit2sMemory limit512 MB
Given start a, end b, and a bidirectional teleporter linking x and y, find the minimum tractor distance to move from a to b, with the option to skip the teleporter.
- Level
Easy2 of 10
- Topics
- Math, Implementation, Brute force, Greedy
- Solved
- No attempts yet
Problem
Of all the chores on the farm, the one Farmer John dislikes most is hauling around lots of cow manure. To cut the work down he built a new machine: the manure teleporter. Instead of carrying manure between two points in a cart behind his tractor, he sends it from one location to another instantly.
Farmer John's farm runs along a single long straight road, so every location on the farm is given by its position along that road, a point on the number line. A teleporter is described by two numbers and . Manure brought to location moves instantly to location , and manure brought to location moves instantly to location .
Farmer John wants to move manure from location to location , and he has built one teleporter that might help. He does not have to use it if it does not help. Determine the minimum total distance he has to haul the manure with his tractor.
Input
The first and only line contains four space separated integers , , and . Here and are the start and the end locations, and and describe the teleporter. Every position is an integer between and , and the positions are not necessarily distinct.
Output
Print one integer, the minimum distance Farmer John has to haul the manure with his tractor.
Note
Take , , and . The best plan is to haul the manure from position 3 to position 2, teleport it to position 8, then haul it from there to position 10. The tractor covers 1 + 2 = 3 in total.