You are the Chief Engineer of a fast growing start-up. You wish to place $K$ servers in some distinct locations from among $N$ locations. The locations, numbered $1, 2, \ldots, N$ are arranged in a circular manner. The distance between every adjacent location is 1 unit. $1$ and $N$ are adjacent. 

You want to place the servers such that the maximum shortest distance between any two adjacent servers is as less as possible. Find this minimum possible distance that can be achieved, and also the minimum number of pairs of adjacent servers separated by this distance.

------ Input: ------

The first line contains a single integer, $T$, denoting the number of test cases.
Each test case consists of a single line containing two space-separated integers $N$ and $K$, denoting the number of locations, and the number of servers, respectively.

------ Output: ------

For test case, output two space-separated integers $D$ and $X$, denoting the minimum possible maximum shortest distance that can be achieved between any two adjacent servers, and the minimum number of pairs of servers separated by this distance, respectively, in a separate line.

------ Constraints  ------
$1 ≤ T ≤ 10^{5}$
$3 ≤ K ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
3

6 3

10 6

10 4
----- Sample Output 1 ------ 
2 3

2 4

3 2
----- explanation 1 ------ 
- Sample Test $1$: Let the locations be numbered from $1$ to $6$. We can place the servers at locations $1$, $3$ and $5$. Thus, the distances between locations $1$ and $3$, $3$ and $5$, and $5$ and $1$ are all $=2$, which is the lowest possible maximum distance that can be achieved here. There are $3$ pairs of locations separated by this distance.

- Sample Test $2$: Let the locations be numbered from $1$ to $10$. We can place the servers at locations $1,2,4,6,8$ and $10$. Thus, the minimum possible maximum distance between any two adjacent servers is $2$. There shall be at least $4$ pairs of servers separated by this distance. Here, they are $(2,4)$, $(4,6)$, $(6,8)$ and $(8,10)$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
from sys import stdin, stdout
from math import log2, ceil, floor
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mod = n % m
	if mod == 0:
		mod = m
	print(ceil(n / m), mod)


test_case = int(input())
for test in range(test_case):
	(num_loc, num_serv) = map(int, input().split())
	(min_poss_max_shdist, min_pair_servers) = (0, 0)
	min_poss_max_shdist = (num_loc + num_serv - 1) // num_serv
	if num_loc % num_serv == 0:
		min_pair_server = num_serv
	else:
		min_pair_server = num_loc - num_serv * (num_loc // num_serv)
	print(min_poss_max_shdist, min_pair_server)


for _ in range(int(input())):
	(noLoc, noServer) = map(int, input().split())
	(minDist, minPair) = (0, 0)
	minDist = (noLoc + noServer - 1) // noServer
	if noLoc % noServer == 0:
		minPair = noServer
	else:
		minPair = noLoc - noServer * (noLoc // noServer)
	print(minDist, minPair)


def ti():
	return tuple(map(int, input().split()))

def li():
	return list(map(int, input().split()))
for tastcas in range(int(input())):
	(n, m) = li()
	t = n / m
	tt = int(t)
	if t == tt:
		print(tt, m)
	else:
		print(tt + 1, n % m)


import math
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	y = n // x
	if n % x == 0:
		print(y, x)
	else:
		z = y * x
		print(y + 1, n - z)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n % k == 0:
		print(-(-n // k), k)
	else:
		print(-(-n // k), n % k)


import math
for _ in range(int(input())):
	(l, s) = map(int, input().split())
	r = l % s
	if r == 0:
		print(l // s, s)
	else:
		print(l // s + 1, r)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	r = n % k
	if r == 0:
		print(n // k, k)
	else:
		print(n // k + 1, r)


import math
t = int(input())
while t != 0:
	(n, k) = list(map(int, input().split()))
	maxi = math.ceil(n / k)
	if n % k != 0:
		count = n - n // k * k
	else:
		count = k
	print(maxi, count)
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if n % k == 0:
		print('{} {}'.format(int(n / k), k))
	else:
		print('{} {}'.format(int(n / k + 1), n % k))


import math
t = int(input())
for i in range(t):
	(D, X) = map(int, input().split())
	ans1 = math.ceil(D / X)
	if D % X == 0:
		print(ans1, X)
	else:
		print(ans1, D % X)


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n % k == 0:
		d = n // k
		p = k
	else:
		d = n // k + 1
		p = n % k
	print(d, p)


import math
for tc in range(int(input())):
	(N, K) = map(int, input().split())
	if N % K == 0:
		print(math.ceil(N / K), K)
	else:
		print(math.ceil(N / K), N % K)


import sys
from math import sqrt, gcd
from collections import deque, Counter, OrderedDict
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	(n, k) = M()
	if n % k == 0:
		print(n // k, k)
		continue
	print(n // k + 1, n - n // k * k)


import math
T = int(input())
for tj in range(T):
	(N, K) = map(int, input().split())
	if K == 2:
		print('1 1')
	else:
		value = math.ceil(N / K)
		if N % K == 0:
			print(value, K)
		else:
			print(value, N % K)


import math
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	x = math.ceil(n / k)
	if n % k == 0:
		print(x, k)
	else:
		print(x, n % k)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	print(math.ceil(n / k), end=' ')
	print(k if n % k == 0 else n % k)


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


try:
	for _ in range(int(input())):
		a = list(map(int, input().split()))
		n = a[0]
		k = a[1]
		if n % k == 0:
			print(n // k, k)
		else:
			print(n // k + 1, n % k)
except:
	pass


import numpy as np
t = int(input())
for i in range(0, t):
	b = list(map(int, input().split()))
	a = np.array(b)
	n = a[0]
	k = a[1]
	if n % k == 0:
		d = n // k
		x = k
		print(d, x)
	else:
		m = n // k
		d = m + 1
		x = n % k
		print(d, x)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	p = math.ceil(n / k)
	q = n % k
	if q == 0:
		q = k
	print(p, ' ', q)


for W in range(int(input())):
	(N, K) = map(int, input().split())
	ans1 = 0
	ans2 = 0
	if N % K > 0:
		ans1 = N // K + 1
	else:
		ans1 = N // K
	if N % K > 0:
		ans2 = N % K
	else:
		ans2 = K
	print(ans1, ans2)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	ans = n // k + (0 if n % k == 0 else 1)
	res = n - n // k * k
	print(ans, res if res != 0 else n // ans)


def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		ans = n // k + (0 if n % k == 0 else 1)
		res = n - n // k * k
		print(ans, res if res != 0 else n // ans)
main()


T = int(input())
for x in range(T):
	(n, k) = map(int, input().split())
	ans = n // k + (0 if n % k == 0 else 1)
	res = n - n // k * k
	print(ans, res if res != 0 else n // ans)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	print(ceil(n / k), end=' ')
	if n % k == 0:
		print(k)
	else:
		print(n % k)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if n % k == 0:
		d = n // k
		x = k
	elif n % k != 0:
		d = n // k + 1
		x = n - (d - 1) * k
	print(d, x)


import math
for x in range(int(input())):
	(N, K) = map(int, input().split())
	if N % K == 0:
		print(N // K, K)
	else:
		j = 1
		i = 0
		while i <= N:
			i = j * K
			j += 1
		print(math.floor(N // K) + 1, N - (j - 2) * K)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if n % k == 0:
		c = n // k
		x = k
	else:
		c = n // k + 1
		x = n - (c - 1) * k
	print(c, x)


from math import ceil
for i in range(int(input())):
	(x, y) = map(int, input().split())
	p = []
	if x % y == 0:
		print(x // y, y)
	else:
		print(ceil(x / y), x % y)


import math
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	(d, c) = (0, 0)
	if a % b == 0:
		c = a // b
		d = b
	else:
		c = a // b + 1
		d = a % b
	print(c, d)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n % k == 0:
		q = n // k
		r = k
	else:
		q = n // k + 1
		r = n % k
	print(q, r)


tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	if n % k == 0:
		d = n // k
		r = k
	else:
		d = n // k + 1
		r = n % k
	print(d, r)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	if n == k:
		print(1, n)
	elif n % k == 0:
		print(n // k, n // (n // k))
	elif n % k != 0:
		print(n // k + 1, n % k)


from math import ceil, floor
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if n % k == 0:
		print(ceil(n / k), k)
	else:
		print(floor(n / k) + 1, n - k * floor(n / k))


t = int(input())
for tt in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	if n % k == 0:
		d = n // k
		x = k
	else:
		d = n // k + 1
		x = n % k
	print(d, x)


T = int(input())
while T != 0:
	(n, k) = map(int, input().split())
	if n % k == 0:
		d = int(n / k)
		x = k
	else:
		d = int(n / k) + 1
		x = n % k
	print(d, x)
	T = T - 1


subtask = int(input())
for _ in range(subtask):
	(N, K) = map(int, input().split())
	if N % K == 0:
		print(N // K, K)
	else:
		print(N // K + 1, N % K)


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


T = int(input())
for tc in range(T):
	(N, K) = map(int, input().split())
	if N / K > int(N / K):
		z = int(N / K) + 1
		x = N % K
		print(z, x)
	else:
		z = int(N / K)
		x = K
		print(z, x)


t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	if n % k == 0:
		k1 = int(n / k)
		p = k
	else:
		k1 = n // k + 1
		p = n - n // k * k
	print(k1, p)