Read problem statements in [Russian] and [Mandarin Chinese].

You are given two integers A, B. You have to choose an integer X in the range [minimum(A, B), maximum(A, B)] such that: 

\Big \lceil \frac{B - X}{2} \Big \rceil + \Big \lceil \frac{X - A}{2} \Big \rceil is maximum. 

What is the maximum sum you can obtain if you choose X optimally?

Note: \lceil x \rceil : Returns the smallest integer that is greater than or equal to x (i.e  rounds up to the nearest integer). For example, \lceil 1.4 \rceil = 2, \lceil 5 \rceil = 5, \lceil -1.5 \rceil = -1, \lceil -3 \rceil = -3 , \lceil 0 \rceil = 0.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains of a single line of input, two integers A, B.

------ Output Format ------ 

For each testcase, output the maximum sum of \lceil \frac{B - X}{2} \rceil + \lceil \frac{X - A}{2} \rceil.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ A, B ≤ 10^{9}$

----- Sample Input 1 ------ 
3
2 2
1 11
13 6

----- Sample Output 1 ------ 
0
6
-3
----- explanation 1 ------ 
- In the first test case, there is only one possible value of $X$ which is equal to $2$. So the sum is equal to $\lceil \frac{2 - 2}{2} \rceil + \lceil \frac{2 - 2}{2} \rceil$ = $\lceil \ 0 \rceil + \lceil \ 0 \rceil$  = $0 + 0 = 0$.
   
- In the second test case, we can choose $X$ to be $2$. So sum is equal to $\lceil \frac{11 - 2}{2} \rceil + \lceil \frac{2 - 1}{2} \rceil$ = $\lceil \ 4.5 \rceil + \lceil \ 0.5 \rceil$ = $5 + 1 = 6$. There is no possible way to choose an integer $X$ in the range $[1, 11]$ such that sum is greater than $6$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
		continue
	x = math.ceil((b - a) / 2)
	y = math.ceil((b - a - 1) / 2) + 1
	print(max(x, y))


import math as mt
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	else:
		x = min(a, b)
		print(max(mt.ceil((b - x) / 2) + mt.ceil((x - a) / 2), mt.ceil((b - x - 1) / 2) + mt.ceil((x + 1 - a) / 2)))


from math import ceil
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	elif b > a:
		print(max(1 + ceil((b - 1 - a) / 2), ceil((b - a) / 2)))
	elif a > b:
		print(max(ceil((b + 1 - a) / 2), ceil((b - a) / 2)))


import math
for _ in range(int(input())):
	(A, B) = list(map(int, input().split()))
	if A == B:
		print('0')
		continue
	(x1, x2) = [min(A, B), min(A, B) + 1]
	ans = max(math.ceil((B - x1) / 2) + math.ceil((x1 - A) / 2), math.ceil((B - x2) / 2) + math.ceil((x2 - A) / 2))
	print(ans)


from math import ceil
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print('0')
	else:
		x = min(a, b)
		print(ceil((b - x - 1) / 2) + ceil((x - a + 1) / 2))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	if b == a:
		print(0)
	elif (b - a) % 2 == 0:
		print((b - a) // 2 + 1)
	else:
		print((b - a + 1) // 2)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	else:
		e = b - a
		if e % 2 == 0:
			print((b - a) // 2 + 1)
		else:
			print((b - a + 1) // 2)


import math
n = int(input())
i = 0
for i in range(n):
	(a, b) = map(int, input().split())
	if a == b:
		res = 0
	if a > b:
		temp = b + 1
		res = math.ceil((b - temp) / 2)
		res = res + math.ceil((temp - a) / 2)
	if b > a:
		temp = a + 1
		res = math.ceil((b - temp) / 2)
		res = res + math.ceil((temp - a) / 2)
	print(res)


import math
t = int(input())
while t > 0:
	t -= 1
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	elif b > a:
		print((b - a) // 2 + 1)
	elif (a - b) % 2 == 1:
		print(-((a - b) // 2))
	else:
		print((b - a) // 2 + 1)


import math
q = int(input())
while q > 0:
	q -= 1
	(a, b) = list(map(int, input().split()))
	if a < b:
		temp = math.ceil((b - a - 1) / 2) + math.ceil((a + 1 - a) / 2)
		print(temp)
	elif a == b:
		print(0)
	else:
		temp = math.ceil((b - b - 1) / 2) + math.ceil((b + 1 - a) / 2)
		print(temp)


import math
t = int(input())
for i in range(1, t + 1):
	(a, b) = map(int, input().strip().split())
	s = []
	if a != b:
		for x in range(a, a + 2):
			first = math.ceil((b - x) / 2)
			part = math.ceil((x - a) / 2)
			sum = first + part
			s.append(sum)
		print(max(s))
	else:
		print(0)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	f = 0
	if a != b:
		c = min(a, b)
		d = max(a, b)
		e = math.ceil((b - c) / 2) + math.ceil((c - a) / 2)
		d = math.ceil((b - (c + 1)) / 2) + math.ceil((c + 1 - a) / 2)
		f = max(e, d)
	else:
		pass
	print(f)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	for _ in tr():
		(a, b) = sm()
		if a == b:
			print(0)
			continue
		case_one = math.ceil((b - a) / 2)
		case_two = math.ceil((b - a - 1) / 2) + 1
		print(max(case_one, case_two))
main()


for i in range(int(input())):
	(x, y) = list(map(int, input().split()))
	if x != y:
		if x % 2 == 0 and y % 2 == 0 or (x % 2 != 0 and y % 2 != 0):
			print((y - (min(x, y) + 1)) // 2 + 1 + (min(x, y) - x) // 2 + 1)
		elif x % 2 == 0 and y % 2 == 1 or (x % 2 != 0 and y % 2 != 1):
			print((y - (min(x, y) + 1)) // 2 + 1 + (min(x, y) + 1 - x) // 2)
	else:
		print(0)


from math import ceil
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	x = min(a, b)
	if a & 1 == 1 and b & 1 == 1:
		if min(a, b) + 1 <= max(a, b):
			x = min(a, b) + 1
	elif a & 1 == 0 and b & 1 == 0:
		if min(a, b) + 1 <= max(a, b):
			x = min(a, b) + 1
	ans = ceil((b - x) / 2) + ceil((x - a) / 2)
	print(ans)


import sys, math
sys.setrecursionlimit(10 ** 5)

def pro(a1, b1):
	(b, a) = (max(a1, b1), min(a1, b1))
	if b == a:
		print(0)
		return
	ans = -math.inf
	for i in range(a, min(b, a + 10)):
		l = math.ceil((b1 - i) / 2)
		r = math.ceil((i - a1) / 2)
		ans = max(ans, l + r)
	print(ans)
n = int(input())
for i in range(n):
	(n, k) = list(map(int, input().split()))
	pro(n, k)


import math
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	else:
		x = min(a, b) + 1
		ans = math.ceil((b - x) / 2) + math.ceil((x - a) / 2)
		print(ans)


for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	if a == b:
		print(0)
	elif b > a:
		print(int((b - a) / 2) + 1)
	elif (a - b) % 2 != 0:
		print(int((b - a) / 2))
	else:
		print(int((b - a) / 2) + 1)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
		continue
	x = min(a, b)
	temp = math.ceil((b - x - 1) / 2)
	temp1 = math.ceil((b - x) / 2)
	temp2 = math.ceil((x - a) / 2)
	temp3 = math.ceil((x + 1 - a) / 2)
	print(max(temp + temp3, temp2 + temp))


import math
u = int(input())
while u != 0:
	(a, b) = map(int, input().split())
	if a == b:
		s = math.ceil(a - b / 2) + math.ceil(a - b / 2)
		print('0')
	else:
		maximum = max(a, b)
		minimum = min(a, b)
		m = minimum + 1
		s = (b - m) / 2
		d = (m - a) / 2
		f = math.ceil(s)
		g = math.ceil(d)
		print(f + g)
	u = u - 1


import math
T = int(input())
for i in range(T):
	(A, B) = map(lambda x: int(x), str(input()).split(' '))
	if A == B:
		print(0)
	else:
		print(math.ceil((B - (A + 1)) / 2) + math.ceil((A + 1 - A) / 2))


import math

def ans(a, b, x):
	return math.ceil((b - x) / 2) + math.ceil((x - a) / 2)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
		continue
	if a % 2 == b % 2:
		print(ans(a, b, min(a, b) + 1))
	else:
		print(ans(a, b, b))


from math import ceil
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	else:
		v = int(ceil((b - a) / 2))
		if abs(b - a) % 2 == 0:
			print(v + 1)
		else:
			print(v)


import math
t = int(input())
while t != 0:
	(a, b) = map(int, input().split())
	if a == b:
		s = math.ceil(a - b / 2) + math.ceil(a - b / 2)
		print('0')
	else:
		mx = max(a, b)
		mn = min(a, b)
		m = mn + 1
		s = (b - m) / 2
		d = (m - a) / 2
		f = math.ceil(s)
		g = math.ceil(d)
		print(f + g)
	t = t - 1


import numpy as np

def ans(a, b):
	if a == b:
		return 0
	elif a > b:
		x = b + 1
		return int(np.ceil((b - x) / 2) + np.ceil((x - a) / 2))
	else:
		x = a + 1
		return int(np.ceil((b - x) / 2) + np.ceil((x - a) / 2))
try:
	for i in range(int(input())):
		(a, b) = map(int, input().split())
		print(ans(a, b))
except:
	pass


try:
	import math
	t = int(input())
	while t != 0:
		(a, b) = map(int, input().split(' '))
		for x in (min(a, b), max(a, b)):
			if x == a and x == b:
				s = (b - x) / 2 + (x - a) / 2
			else:
				s = (b - x + 1) / 2 + (x - a + 1) / 2
		print(math.floor(s))
except:
	pass


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
		continue
	if a < b:
		con = b - 1
	else:
		con = a - 1
	print(math.ceil((b - con) / 2) + math.ceil((con - a) / 2))


def ceilsum(a, b):
	if a == b:
		return 0
	elif a % 2 != b % 2:
		return (b - a + 1) // 2
	else:
		return (b - a + 2) // 2
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(ceilsum(a, b))


def inp():
	return int(input())
import math
for t in range(inp()):
	(a, b) = list(map(int, input().split(' ')))
	if a == b:
		print(0)
	elif a < b:
		if a % 2 != 0 and b % 2 == 0 or (a % 2 == 0 and b % 2 != 0):
			print((b - a) // 2 + 1)
		else:
			print((b - a) // 2 + 1)
	else:
		value = (a + b) // 2
		another = value + 1
		res = math.ceil((b - value) / 2) + math.ceil((value - a) / 2)
		res1 = math.ceil((b - another) / 2) + math.ceil((another - a) / 2)
		print(max(res, res1))


import math
t = int(input())
while t:
	(a, b) = map(int, input().split())
	if a == b:
		res = 0
	if a > b:
		temp = b + 1
		res = math.ceil((b - temp) / 2)
		res += math.ceil((temp - a) / 2)
	if b > a:
		temp = a + 1
		res = math.ceil((b - temp) / 2)
		res += math.ceil((temp - a) / 2)
	print(res)
	t -= 1


t = int(input())
sol = []
for tc in range(t):
	(a, b) = map(int, input().split(' '))
	max = 0
	if b != a:
		if b % 2 != 0 and a % 2 != 0 or (b % 2 == 0 and a % 2 == 0):
			max = (b - a) / 2 + 1
		else:
			max = (b - a + 1) / 2
	else:
		max = 0
	sol.append(max)
for r in sol:
	print(int(r))


import math
q = int(input())
for i in range(q):
	(a, b) = list(map(int, input().split()))
	if a == b:
		x = a
	else:
		x = min(a, b) + 1
	m = math.ceil((b - x) / 2) + math.ceil((x - a) / 2)
	print(m)


t = int(input())
for z in range(t):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	elif b > a:
		print((b - a) // 2 + 1)
	elif (a - b) % 2 == 0:
		print((b - a) // 2 + 1)
	else:
		print((b - a) // 2 + 1)


import math
for x in range(int(input())):
	(A, B) = map(int, input().split())
	if A == B:
		print(0)
	elif A > B:
		if (B - A) % 2 == 1:
			print(math.ceil((B - A) / 2))
		else:
			print(math.ceil((B - A) // 2) + 1)
	elif A < B:
		print(math.ceil((B - A) // 2) + 1)


import math

def fun(a, b):
	if a == b:
		return 0
	else:
		ans = math.ceil((b - (a + 1)) / 2) + 1
		return ans
testCases = int(input())
for i in range(testCases):
	(a, b) = map(int, input().split())
	print(fun(a, b))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	import math
	if a == b:
		print('0')
	if a > b:
		c = b + 1
		d = math.ceil((b - c) / 2)
		e = math.ceil((c - a) / 2)
		print(d + e)
	if b > a:
		c = a + 1
		d = math.ceil((b - c) / 2)
		e = math.ceil((c - a) / 2)
		print(d + e)


import math as math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	x = 0
	if a == b:
		print(0)
		continue
	elif a > b:
		x = b + 1
	elif b > a:
		x = a + 1
	print(math.ceil((b - x) / 2) + math.ceil((x - a) / 2))


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = min(a, b)
	r = max(a, b)
	if a == b:
		ans = 0
	else:
		if a < b:
			v1 = a + 1
			v2 = b - 1
		else:
			c = a + b
			if c % 2 == 0:
				v1 = c / 2
				v2 = v1 - 1
			else:
				v1 = math.ceil((a + b) / 2)
				v2 = math.floor((a + b) / 2)
		t1 = math.ceil((b - v1) / 2) + math.ceil((v1 - a) / 2)
		t2 = math.ceil((b - v2) / 2) + math.ceil((v2 - a) / 2)
		ans = max(t1, t2)
	print(ans)


import math
I = int(input())
e = []
for Z in range(I):
	(A, B) = map(int, input().split())
	if A == B:
		X = A
	elif A > B:
		X = A - 1
	else:
		X = B - 1
	S = math.ceil((B - X) / 2) + math.ceil((X - A) / 2)
	e.append(S)
for X in e:
	print(X)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	res = 0
	if a == b:
		res = 0
	elif b > a:
		res = int((b - a) / 2) + 1
	elif a > b:
		val = a - b
		if val % 2 == 0:
			res = int((b - a) / 2) + 1
		else:
			res = int((b - a) / 2)
	print(res)