Read problems statements in mandarin chinese, russian and vietnamese as well. 

On the occasion of the birthday, Chef bought a large circular cake and decorated it with  k  candles placed equally spaced around the circumference of the cake, i.e. the lengths of the arcs that connect any two adjacent candles are equal. 

Chef enumerated the candles from  1 to  k  in clockwise manner. He then chose two candles, say  A  and  B  and lit them up. Now, he left the kitchen and decided to come back in some time with friends to celebrate the birthday.

Meanwhile Chef's little brother came to the kitchen and saw the cake. He wants to light up one of the not lit candles C such that angle  ACB  is an obtuse angle. He believes that such a pattern of lit candles will be auspicious. Can you find out how many candles C he can light up?

------ Input ------ 

The first line contains a single integer T, the number of test cases. Each test case is described by a single line containing three space-separated integers k, A, B. 

------ Output ------ 

For each test case, output a single line containing one integer: the answer for the test case.

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

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

----- Sample Input 1 ------ 
3
6 1 3
6 1 4
10 1 5
----- Sample Output 1 ------ 
1
0
3
----- explanation 1 ------ 
Example case 1. Only candle with number 2 is suitable.
Example case 2. No matter how we choose C the angle would have 90 degrees.
Example case 3. Candles with numbers 2,3,4 are suitable.

Difficulty: MEDIUM_HARD
Tags: Geometry

Mathematics

Starter code:

Solutions:
def soln(n: int, a: int, b: int) -> int:
	x = min(a, b)
	y = max(a, b)
	side_a = y - x - 1
	side_b = n - (y - x + 1)
	if side_a == side_b:
		return 0
	return min(side_a, side_b)
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	print(soln(n, a, b))


for _ in range(int(input())):
	(k, a, b) = map(int, input().split())
	nm = int(abs(b - a))
	if k % 2 == 0 and nm == k // 2:
		print(0)
	else:
		a = nm - 1
		b = k - (a + 2)
		print(min(a, b))


t = int(input())
for tc in range(t):
	(k, A, B) = map(int, input().split())
	c = abs(A - B) - 1
	d = k - c - 2
	s = k & 1
	if c + 1 == k // 2 and ~s + 2:
		print(0)
	else:
		print(min(c, d))


t = int(input())
for i in range(t):
	(k, a, b) = map(int, input().split())
	c = abs(a - b) - 1
	d = k - c - 2
	s = k & 1
	print(0 if c + 1 == k // 2 and ~s + 2 else min(c, d))


try:
	for _ in range(int(input())):
		(k, a, b) = map(int, input().split())
		if a > b:
			t = a
			a = b
			b = t
		if b - a == k / 2:
			print(0)
		elif b - a < k / 2:
			print(b - a - 1)
		else:
			print(k + a - b - 1)
except EOFError:
	pass


for _ in range(int(input())):
	(k, a, b) = map(int, input().split())
	n = abs(a - b)
	m = k - max(a, b)
	if not k & 1 and n == k // 2:
		print(0)
	else:
		print(min(n - 1, min(a, b) - 1 + k - max(a, b)))


test = int(input())
for _ in range(test):
	(a, b, c) = map(int, input().split())
	d = 360 / a
	e = abs(b - c)
	d = d * e
	f = a - e
	if f == e:
		print(0)
	else:
		print(min(f, e) - 1)


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


for _ in range(int(input())):
	(k, A, B) = map(int, input().split())
	if k % 2 == 0 and abs(A - B) == k // 2:
		print(0)
	else:
		p = abs(A - B) - 1
		q = k - p - 2
		print(min(p, q))


from collections import defaultdict as dd
from collections import Counter as ccd
from itertools import permutations as pp
from itertools import combinations as cc
from random import randint as rd
from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq as hq
mod = pow(10, 9) + 7

def inp(flag=0):
	if flag == 0:
		return list(map(int, input().strip().split(' ')))
	else:
		return int(input())
t = inp(1)
while t:
	t -= 1
	(k, a, b) = inp()
	(a, b) = (min(a, b), max(a, b))
	n1 = b - a - 1
	n2 = k - b + a - 1
	if n1 != n2:
		print(min(n1, n2))
	else:
		print(0)


from math import *
from string import *
from itertools import *
T = int(input())
for _ in range(T):
	(K, A, B) = map(int, input().split())
	A -= 1
	B -= 1
	ans = 0
	if A > B:
		A = A ^ B
		B = A ^ B
		A = A ^ B
	if not (K & 1 == 0 and B - A == K // 2 and (K % (B - A) == 0)):
		ans = min(B - A, K - (B - A))
	if ans == 0:
		print(ans)
	else:
		print(ans - 1)


for _ in range(int(input())):
	(k, a, b) = map(int, input().split())
	diff = abs(a - b)
	diff = min(diff, k - diff)
	if diff == k - diff:
		print('0')
	else:
		print(diff - 1)


t = int(input())

def renumber(a, b):
	if b - a < k / 2:
		(d, c) = (b - a + 1, 1)
	else:
		(d, c) = (a + k - b + 1, 1)
	return (c, d)
for _ in range(t):
	(k, a, b) = map(int, input().split())
	if a < b:
		(a, b) = renumber(a, b)
	else:
		(a, b) = renumber(b, a)
	if b - a == k / 2:
		print('0')
	else:
		print(str(b - a - 1))


import math
sq = math.sqrt
cl = math.ceil
fl = math.floor
lg = math.log
mod = 1000000007

def main():
	T = int(input())
	for _ in range(T):
		(k, a, b) = map(int, input().split())
		ans = None
		dif = abs(a - b)
		if dif > k // 2:
			dif = k - dif
		if dif * 2 == k:
			print(0)
		else:
			print(dif - 1)
main()


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


for _ in range(int(input())):
	(k, a, b) = map(int, input().split())
	d = abs(a - b)
	if a > b:
		(a, b) = (b, a)
	(q1, q2) = (1, b - (a - 1))
	sec_part = k / 2 + 1
	fir_part = q2
	if fir_part == sec_part:
		real_ans = 0
	elif fir_part < sec_part:
		real_ans = q2 - q1 - 1
	else:
		real_ans = k - q2
	div = 360 // k
	ang = div * d
	if ang == 180:
		ans = 0
	elif ang > 180:
		ans = k - 1 - abs(b - a)
		if ans != real_ans:
			wow
	else:
		ans = abs(b - a) - 1
	print(real_ans)


for _ in range(int(input())):
	(k, a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	(q1, q2) = (1, b - (a - 1))
	sec_part = k / 2 + 1
	fir_part = q2
	if fir_part == sec_part:
		print(0)
	elif fir_part < sec_part:
		print(q2 - q1 - 1)
	else:
		print(k - q2)


T = int(input())
for i in range(T):
	(k, A, B) = map(int, input().split())
	if A > B:
		(A, B) = (B, A)
	a = 1
	b = B - (A - 1)
	if b < k / 2 + 1:
		ans = b - a - 1
	if b == k / 2 + 1:
		ans = 0
	if b > k / 2 + 1:
		ans = k - b
	print(ans)


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


for _ in range(int(input())):
	(k, a, b) = map(int, input().split())
	aob_num = 360 * abs(b - a)
	aob_den = k
	if aob_num == aob_den * 180:
		print(0)
	elif aob_num > aob_den * 180:
		print(k - (abs(b - a) + 1))
	else:
		print(abs(b - a) - 1)


t = int(input())
for i in range(t):
	(k, a, b) = map(int, input().split())
	z = abs(b - a)
	p = k - z
	if z == p:
		print(0)
	else:
		print(min(p, z) - 1)


t = int(input())
for ijk in range(0, t):
	(k, a, b) = map(int, input().strip().split())
	if k % 2 == 0 and abs(b - a) == k / 2:
		print(0)
	else:
		print(min(abs(b - a) - 1, abs(k - abs(b - a) - 1)))


t = int(input(''))
for case in range(0, t):
	nums = input('')
	nums = nums.split()
	nums = [int(num) for num in nums]
	k = nums[0]
	a = nums[1]
	b = nums[2]
	if k % 2:
		if abs(a - b) > k // 2:
			print(k - abs(a - b) - 1)
		else:
			print(abs(a - b) - 1)
	elif abs(a - b) == k // 2:
		print('0')
	elif abs(a - b) > k // 2:
		print(k - abs(a - b) - 1)
	else:
		print(abs(a - b) - 1)


for t in range(int(input())):
	temp = list(map(int, input().split()))
	k = temp[0]
	a = temp[1]
	b = temp[2]
	if a > b:
		q = a
		a = b
		b = q
	val = 180 * (b - a)
	val /= k
	if val < 90:
		ans = b - a - 1
	elif val > 90:
		ans = k - (b - a + 1)
	elif val == 90:
		ans = 0
	print(ans)


t = int(input())
for _ in range(t):
	(k, a, b) = map(int, input().split())
	d = abs(a - b)
	if k % 2 == 0 and d == k / 2:
		print('0')
	else:
		if d > k // 2:
			print(k - d - 1)
		if d <= k // 2:
			print(d - 1)


t = int(input())
for i in range(t):
	(k, a, b) = map(int, input().split())
	c = abs(b - a)
	flag = 0
	anti = c - 1
	clock = k - c - 1
	if k % 2 == 0:
		if c == k // 2:
			flag = 1
	if flag == 1:
		print('0')
	elif anti > clock:
		print(clock)
	else:
		print(anti)


t = int(input())
for i in range(t):
	A = list(map(int, input().split()))
	p = A[0] / 2
	a = max(A[1], A[2])
	b = min(A[1], A[2])
	if a - b < p:
		ans = a - b - 1
	elif a - b > p:
		ans = A[0] - a + b - 1
	else:
		ans = 0
	print(ans)


T = int(input())
for i in range(0, T):
	(k, A, B) = map(int, input().split())
	p = k / 2
	a = max(A, B)
	b = min(A, B)
	if a - b < p:
		ans = a - b - 1
	elif a - b > p:
		ans = k - a + b - 1
	else:
		ans = 0
	print('%d' % ans)


t = int(input())
while t:
	t -= 1
	(k, a, b) = map(int, input().split())
	y = abs(b - a) - 1
	x = abs(k - y) - 2
	if x == y:
		print(0)
	else:
		print(min(x, y))


t = int(input())
while t > 0:
	t -= 1
	(k, a, b) = map(int, input().strip().split(' '))
	if a > b:
		tmp = b
		b = a
		a = tmp
	ratio = (b - a) / k
	if ratio == 0.5:
		candles = 0
	elif ratio > 0.5:
		candles = a + k - b - 1
	else:
		candles = b - a - 1
	print(str(candles))


for i in range(int(input().strip())):
	(n, a, b) = tuple(map(int, input().strip().split()))
	c = abs(b - a) - 1
	if n - 2 != c * 2:
		print(min(n - 2 - c, c))
	else:
		print(0)


for x in range(int(input())):
	(k, a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	inside = b - a - 1
	outside = k - inside - 2
	if not k & 1 and b - a == k // 2:
		print(0)
	else:
		print(min(inside, outside))


t = int(input())
for i in range(t):
	(k, a, b) = map(int, input().split())
	n1 = min(a, b)
	n2 = max(a, b)
	if k % 2 is 0:
		if n2 - n1 == k // 2:
			print('0')
		elif n2 - n1 > k // 2:
			n1 = n1 + 2 * (n2 - n1 - k // 2)
			print(n2 - n1 - 1)
		else:
			print(n2 - n1 - 1)
	elif n2 - n1 > k // 2:
		n1 = n1 + 2 * (n2 - n1 - k // 2) - 1
		print(n2 - n1 - 1)
	else:
		print(n2 - n1 - 1)


def mx(a, b):
	if a > b:
		return a
	else:
		return b

def mn(a, b):
	if a > b:
		return b
	else:
		return a
t = int(input())
while t:
	lis = list(input().split(' '))
	a = int(lis[0])
	b = int(lis[1])
	c = int(lis[2])
	num = mx(b, c)
	tum = mn(b, c)
	if a - num + tum - 1 != num - tum - 1:
		mom = min(a - num + tum - 1, num - tum - 1)
		print(mom)
	else:
		print('0')
	t -= 1


t = int(input())
while t > 0:
	t -= 1
	(k, a, b) = map(int, input().split())
	angle = 360.0 / k
	m = abs(a - b)
	n = k - m
	if m == n:
		print('0')
	else:
		print(min(m, n) - 1)


for _ in range(int(input())):
	(c, a, b) = map(int, input().split())
	x = max(a, b) - min(a, b) - 1
	y = c - (max(a, b) - min(a, b) + 1)
	if x < y:
		print(x)
	elif y < x:
		print(y)
	else:
		print(0)


q = int(input())
while q > 0:
	(k, a, b) = input().split()
	(k, a, b) = (int(k), int(a), int(b))
	if a > b:
		(a, b) = (b, a)
	if k % 2 == 0 and b - a == k // 2:
		print('0')
	else:
		print(min(b - a, k - b + a) - 1)
	q -= 1


for t in range(int(input())):
	(k, a, b) = map(int, input('').split())
	if not k & 1 and abs(a - b) == k / 2:
		print(0)
	else:
		print(min(abs(a - b) - 1, min(a, b) - 1 + k - max(a, b)))


for test in range(int(input())):
	(k, a, b) = tuple(map(int, input().split()))
	if b < a:
		(a, b) = (b, a)
	b = b - (a - 1)
	a = 1
	temp = k / 2 + 1
	if b == temp:
		print(0)
	elif b < temp:
		print(b - a - 1)
	else:
		print(k - b)


from math import sqrt
t = int(input())
while t:
	t = t - 1
	(n, a, b) = input().split()
	(n, a, b) = (int(n), int(a), int(b))
	angle = 360 / n
	v1 = min(a, b)
	v2 = max(a, b)
	if n % 2 == 0:
		if v2 - v1 == n // 2:
			print(0)
		else:
			print(min(v2 - v1 - 1, abs(n - v2 + v1 - 1)))
	else:
		print(min(v2 - v1 - 1, abs(n - v2 + v1 - 1)))


for T in range(int(input())):
	(k, A, B) = [int(s) for s in input().split()]
	if B < A:
		C = B
		B = A
		A = C
	x = 360 / k * (B - A)
	y = 1e-09
	if x <= 180 + y and x >= 180 - y:
		ans = 0
	elif x < 180:
		ans = B - A - 1
	else:
		ans = k - (B - A + 1)
	print(ans)


t = int(input())
while t:
	t -= 1
	(k, A, B) = list(map(int, input().split()))
	q = k - (max(A, B) - min(A, B) - 1) - 2
	p = max(A, B) - min(A, B) - 1
	if p == q:
		print('0')
	else:
		print(min(p, q))


from math import pi
t = int(input())
while t > 0:
	(k, A, B) = input().split()
	k = int(k)
	A = int(A)
	B = int(B)
	if B < A:
		C = B
		B = A
		A = C
	x = 360 / k * (B - A)
	eps = 1e-09
	if x <= 180 + eps and x >= 180 - eps:
		ans = 0
	elif x < 180:
		ans = B - A - 1
	else:
		ans = k - (B - A + 1)
	print(ans)
	t -= 1


import sys
T = int(input())
for index in range(1, T + 1):
	(N, A, B) = list(map(int, input().split(' ')))
	half = N / 2
	diff = abs(B - A)
	if diff == half:
		print(0)
	elif diff > half:
		print(N - diff - 1)
	else:
		print(diff - 1)


t = int(input(''))
for x in range(0, t):
	(n, ka, kb) = list(map(int, input().split()))
	a = min(ka, kb)
	b = max(ka, kb)
	if b - a == n / 2:
		print(0)
	elif b - a < n / 2:
		print(b - a - 1)
	else:
		print(a + n - b - 1)


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	if abs(a - b) == 1:
		print(0)
	elif n % 2 == 0 and abs(a - b) == n // 2:
		print(0)
	else:
		ans = abs(a - b)
		if ans < n // 2 + 1:
			print(ans - 1)
		else:
			print(n - ans - 1)


n = int(input())
b = []
for i in range(n):
	a = list(map(int, input().split()))
	b.append(a)
for i in range(n):
	n = b[i][0]
	v1 = b[i][1]
	v2 = b[i][2]
	t = v2 - v1
	if t < 0:
		t = t * -1
	if n % 2 == 0:
		n2 = int(n / 2)
		t = t - n2
		if t < 0:
			t = t * -1
		if t == n2 - 1 or t == 0:
			print(0)
		else:
			print(n2 - t - 1)
	else:
		n2 = int(n / 2)
		if t <= n2:
			print(t - 1)
		else:
			print(n - t - 1)


t = int(input())
for pq in range(t):
	t1 = list(map(int, input().split()))
	n = t1[0]
	a = t1[1]
	b = t1[2]
	if a > b:
		(b, a) = (a, b)
	val = b - a
	if val == n / 2 and n % 2 == 0:
		print(0)
	elif val <= n / 2:
		print(b - a - 1)
	else:
		print(n - b + a - 1)


import math
t = int(input())
for i in range(t):
	(n, x, y) = map(int, input().split())
	a = min(x, y)
	b = max(x, y)
	b = b - a + 1
	a = 1
	if n % 2 == 0 and n / 2 == b - a or (b - a == 1 or b == n):
		print('0')
	elif b > n / 2 + 1:
		print(n - b)
	elif b < n / 2 + 1:
		print(b - 2)


T = int(input())
for i in range(T):
	(k, a, b) = map(int, input().strip().split(' '))
	(c, d) = (max(a, b), min(a, b))
	if k < 5:
		print(0)
	elif k % 2 == 0:
		if c < int(k / 2) + d:
			print(c - d - 1)
		elif c > int(k / 2) + d:
			print(k - c + d - 1)
		elif c == int(k / 2) + d:
			print(0)
	elif c == k and d == 1:
		print(0)
	elif c <= int(k / 2) + d:
		print(c - d - 1)
	elif c > int(k / 2) + d:
		print(k - c + d - 1)


for _ in range(int(input())):
	(k, A, B) = map(int, input().split())
	(A, B) = (min(A, B), max(A, B))
	(A, B) = (1, B - A + 1)
	if k % 2 == 0:
		if B == k // 2 + 1:
			print(0)
			continue
	print(min(B - 2, k - B))


T = int(input().strip())
while T != 0:
	T -= 1
	(k, a, b) = map(int, input().strip().split())
	if b < a:
		temp = b
		b = a
		a = temp
	if (b - a) % k == k / 2:
		ans = 0
	elif (b - a) % k < k / 2:
		ans = b - a - 1
	else:
		ans = k - b + a - 1
	print(ans)


import math

def check(lst):
	k = lst[0]
	A = lst[1]
	B = lst[2]
	if B < A:
		C = B
		B = A
		A = C
	s = 0
	if k % 2 == 0 and B == A + k / 2:
		return 0
	elif k % 2 == 0 and B < A + k / 2:
		s = B - (A + 1)
		return s
	elif k % 2 == 0 and B > A + k / 2:
		s = k - 1 - B + A
		return s
	elif k % 2 == 1 and B < A + k / 2:
		s = B - (A + 1)
		return s
	elif k % 2 == 1 and B > A + k / 2:
		s = k - 1 - B + A
		return s

def main():
	t = int(input(''))
	ans = []
	for i in range(0, t):
		lst = []
		lst = input('').split()
		lst = list(map(int, lst))
		s = check(lst)
		ans.append(s)
	for (idx, item) in enumerate(ans):
		print(ans[idx])
main()


import math
t = int(input())
for i in range(t):
	n = 0
	lis = list()
	(k, a, b) = map(int, input().split())
	if a > b:
		a = a + b
		b = a - b
		a = a - b
	if b - a > k / 2:
		n = k - b + a - 1
	elif b - a < k / 2:
		n = b - a - 1
	print(n)


t = int(input())
for i in range(t):
	(k, a, b) = [int(x) for x in input().split()]
	p1 = abs(b - a) - 1
	p2 = k - abs(b - a) - 1
	if p1 < p2:
		print(p1)
	elif p1 > p2:
		print(p2)
	else:
		print('0')


t = int(input())
while t != 0:
	(n, a, b) = list(map(int, input().split()))
	p = max(a, b) - min(a, b)
	if n % 2 == 0:
		if p == n // 2:
			print(0)
		elif p < n // 2:
			print(p - 1)
		else:
			print(n - p - 1)
	elif p <= n // 2:
		print(p - 1)
	else:
		print(n - p - 1)
	t -= 1


from math import sqrt
T = int(input())
for _ in range(T):
	(K, A, B) = [int(x) for x in input().split()]
	(A, B) = (min(A, B), max(A, B))
	if B - A < K / 2:
		smallerCandles = B - A - 1
		biggerCandles = K - smallerCandles - 2
	elif B - A > K / 2:
		smallerCandles = A + K - B - 1
		biggerCandles = K - smallerCandles - 2
	else:
		smallerCandles = 0
	print(smallerCandles)


import math
testcase = input()
candles = 0
for i in range(int(testcase)):
	arr = [int(x) for x in input().split()]
	if abs(arr[2] - arr[1]) - 1 < int((arr[0] - 1) / 2):
		candles += abs(arr[2] - arr[1]) - 1
	elif arr[0] - (abs(arr[2] - arr[1]) + 1) < int((arr[0] - 1) / 2):
		candles += arr[0] - (abs(arr[2] - arr[1]) + 1)
	print(candles)
	candles = 0


t = int(int(input()))
for i in range(t):
	(k, a, b) = (int(x) for x in input().split())
	if a > b:
		(a, b) = (b, a)
	if k % 2 == 0:
		if b - a < k / 2:
			print(b - a - 1)
		elif b - a > k / 2:
			print(k - b + a - 1)
		else:
			print('0')
	elif k % 2 == 1:
		if b - a <= k / 2:
			print(b - a - 1)
		elif b - a > k / 2:
			print(k - b + a - 1)


from math import floor
t = int(input().strip())
while t:
	t -= 1
	(k, A, B) = map(int, input().strip().split())
	diff = abs(B - A) if abs(B - A) < k / 2 else k - abs(A - B)
	if diff == k / 2 or k <= 4:
		print(0)
	else:
		print(diff - 1)


t = int(input())
for i in range(t):
	(k, a, b) = list(map(int, input().split()))
	(a, b) = (min(a, b), max(a, b))
	b = b - (a - 1)
	a = 1
	l1 = b - a - 1
	l2 = k - l1 - 2
	if l1 == l2:
		print('0')
	else:
		print(min(l1, l2))