Thermostat (Codeforces 1759C)
Tags: Greedy, shortest paths

Vlad came home and found out that someone had reconfigured the old thermostat to the temperature of $$$a$$$.The thermostat can only be set to a temperature from $$$l$$$ to $$$r$$$ inclusive, the temperature cannot change by less than $$$x$$$. Formally, in one operation you can reconfigure the thermostat from temperature $$$a$$$ to temperature $$$b$$$ if $$$|a - b| \ge x$$$ and $$$l \le b \le r$$$.You are given $$$l$$$, $$$r$$$, $$$x$$$, $$$a$$$ and $$$b$$$. Find the minimum number of operations required to get temperature $$$b$$$ from temperature $$$a$$$, or say that it is impossible.

Input: The first line of input data contains the single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.The descriptions of the test cases follow.The first line of each case contains three integers $$$l$$$, $$$r$$$ and $$$x$$$ ($$$-10^9 \le l \le r \le 10^9$$$, $$$1 \le x \le 10^9$$$) — range of temperature and minimum temperature change.The second line of each case contains two integers $$$a$$$ and $$$b$$$ ($$$l \le a, b \le r$$$) — the initial and final temperatures.

Output: Output $$$t$$$ numbers, each of which is the answer to the corresponding test case. If it is impossible to achieve the temperature $$$b$$$, output -1, otherwise output the minimum number of operations.

Note: In the first example, the thermostat is already set up correctly.In the second example, you can achieve the desired temperature as follows: $$$4 \rightarrow 10 \rightarrow 5$$$.In the third example, you can achieve the desired temperature as follows: $$$3 \rightarrow 8 \rightarrow 2 \rightarrow 7$$$.In the fourth test, it is impossible to make any operation.

Sample Inputs:
10
3 5 6
3 3
0 15 5
4 5
0 10 5
3 7
3 5 6
3 4
-10 10 11
-5 6
-3 3 4
1 0
-5 10 8
9 2
1 5 1
2 5
-1 4 3
0 2
-6 3 6
-1 -4

Sample Outputs:
0
2
3
-1
1
-1
3
1
3
-1

Solution (Python):
import sys
input = sys.stdin.readline
import math
''
t = int(input())
for _ in range(t):
    (l, r, x) = list(map(int, input().split()))
    (a, b) = list(map(int, input().split()))
    if abs(a - b) == 0:
        print(0)
    elif abs(a - b) >= x:
        print(1)
    elif r - max(a, b) >= x or min(a, b) - l >= x:
        print(2)
    elif r - a >= x and b - l >= x or (a - l >= x and r - b >= x):
        print(3)
    else:
        print(-1)

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import groupby
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    (l, r, x) = map(int, readline().split())
    (a, b) = map(int, readline().split())
    (bl, br) = (b - l, r - b)
    (al, ar) = (a - l, r - a)
    if a == b:
        print(0)
    elif bl < x and br < x or (al < x and ar < x):
        print(-1)
    elif abs(a - b) >= x:
        print(1)
    elif bl >= x:
        if br >= x:
            print(2)
        elif al < x:
            print(3)
        else:
            print(2)
    elif ar < x:
        print(3)
    else:
        print(2)

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    (l, r, x) = map(int, input().split())
    (a, b) = map(int, input().split())
    if a == b:
        print(0)
    elif abs(r - l) < x:
        print(-1)
    elif abs(l - a) < x and abs(r - a) < x:
        print(-1)
    elif abs(l - b) < x and abs(r - b) < x:
        print(-1)
    elif abs(a - b) >= x:
        print(1)
    elif abs(l - a) >= x and abs(l - b) >= x:
        print(2)
    elif abs(r - a) >= x and abs(r - b) >= x:
        print(2)
    else:
        print(3)