Line Trip (Codeforces 1901A)
Tags: Greedy, math

There is a road, which can be represented as a number line. You are located in the point $$$0$$$ of the number line, and you want to travel from the point $$$0$$$ to the point $$$x$$$, and back to the point $$$0$$$.You travel by car, which spends $$$1$$$ liter of gasoline per $$$1$$$ unit of distance travelled. When you start at the point $$$0$$$, your car is fully fueled (its gas tank contains the maximum possible amount of fuel).There are $$$n$$$ gas stations, located in points $$$a_1, a_2, \dots, a_n$$$. When you arrive at a gas station, you fully refuel your car. Note that you can refuel only at gas stations, and there are no gas stations in points $$$0$$$ and $$$x$$$.You have to calculate the minimum possible volume of the gas tank in your car (in liters) that will allow you to travel from the point $$$0$$$ to the point $$$x$$$ and back to the point $$$0$$$.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.Each test case consists of two lines:  the first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 50$$$; $$$2 \le x \le 100$$$);  the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 < a_1 < a_2 < \dots < a_n < x$$$). 

Output: For each test case, print one integer — the minimum possible volume of the gas tank in your car that will allow you to travel from the point $$$0$$$ to the point $$$x$$$ and back.

Note: In the first test case of the example, if the car has a gas tank of $$$4$$$ liters, you can travel to $$$x$$$ and back as follows:  travel to the point $$$1$$$, then your car's gas tank contains $$$3$$$ liters of fuel;  refuel at the point $$$1$$$, then your car's gas tank contains $$$4$$$ liters of fuel;  travel to the point $$$2$$$, then your car's gas tank contains $$$3$$$ liters of fuel;  refuel at the point $$$2$$$, then your car's gas tank contains $$$4$$$ liters of fuel;  travel to the point $$$5$$$, then your car's gas tank contains $$$1$$$ liter of fuel;  refuel at the point $$$5$$$, then your car's gas tank contains $$$4$$$ liters of fuel;  travel to the point $$$7$$$, then your car's gas tank contains $$$2$$$ liters of fuel;  travel to the point $$$5$$$, then your car's gas tank contains $$$0$$$ liters of fuel;  refuel at the point $$$5$$$, then your car's gas tank contains $$$4$$$ liters of fuel;  travel to the point $$$2$$$, then your car's gas tank contains $$$1$$$ liter of fuel;  refuel at the point $$$2$$$, then your car's gas tank contains $$$4$$$ liters of fuel;  travel to the point $$$1$$$, then your car's gas tank contains $$$3$$$ liters of fuel;  refuel at the point $$$1$$$, then your car's gas tank contains $$$4$$$ liters of fuel;  travel to the point $$$0$$$, then your car's gas tank contains $$$3$$$ liters of fuel. 

Sample Inputs:
3
3 7
1 2 5
3 6
1 2 5
1 10
7

Sample Outputs:
4
3
7

Solution (Python):
def main():
    time = int(input())
    for _ in range(time):
        (n, m) = map(int, input().split())
        arr = list(map(int, input().split()))
        maximum = 0
        j = 0
        for i in range(n):
            A = arr[i] - j
            maximum = max(A, maximum)
            j = arr[i]
        B = (m - arr[n - 1]) * 2
        maximum = max(maximum, B)
        print(maximum)
if __name__ == '__main__':
    main()

Solution (Python):
def x():
    (n, x) = map(int, input().split())
    a = [0] + [*map(int, input().split())]
    a.append(x)
    m = 0
    for (i, j) in zip(a, a[1:]):
        m = max(m, j - i)
    return max(m, 2 * (x - a[-2]))
t = int(input())
b = []
for _ in range(t):
    b.append(x())
print('\n'.join((str(i) for i in b)))

Solution (Python):
t = int(input())
for i in range(t):
    (r, d) = map(int, input().split())
    lst = list(map(int, input().split()))
    ans = [lst[0]]
    if r > 1:
        for j in range(0, r - 1):
            s1 = lst[j + 1] - lst[j]
            ans.append(s1)
        s2 = 2 * (d - lst[-1])
        ans.append(s2)
    else:
        s1 = 2 * (d - lst[0])
        ans.append(s1)
    print(max(ans))