Two cheeky thieves (Chef being one of them, the more talented one of course) have came across each other in the underground vault of the State Bank of Churuland. They are shocked! Indeed, neither expect to meet a colleague in such a place with the same intentions to carry away all the money collected during Churufest 2015.

They have carefully counted a total of exactly 1 billion (109) dollars in the bank vault. Now they must decide how to divide the booty. But there is one problem: the thieves have only M minutes to leave the bank before the police arrives. Also, the more time they spend in the vault, the less amount could carry away from the bank. Formally speaking, they can get away with all of the billion dollars right now, but after t minutes they can carry away only  1 billion * pt dollars, where p is some non-negative constant less than or equal to unity, and at t = M, they get arrested and lose all the money.
They will not leave the vault until a decision on how to divide the money has been made.

The money division process proceeds in the following way: at the beginning of each minute starting from the 1st (that is, t = 0), one of them proposes his own way to divide the booty. If his colleague agrees, they leave the bank with pockets filled with the proposed amounts of dollars. If not, the other one proposes his way at the next minute etc. To escape arrest, they can only propose plans till the beginning of the Mth minute (i.e., till t = M-1).
Each thief wants to maximize his earnings, but if there are two plans with the same amounts for him, he would choose the one which leads to a larger total amount of stolen dollars.

Chef is about to start this procedure, and he is the first to propose a plan. You are wondering what will be the final division of money, if each thief chooses the optimal way for himself and money is considering real.

-----Input-----
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The only line of input for each test case contains an integer M denoting the number of minutes until arrest and a double denoting the constant p.

-----Output-----
For each test case, output a single line containing two space-separated doubles denoting the amount of dollars each thief will get in the optimal division. First number: dollars amassed by Chef, and second: by his colleague. The answer will be considered correct if its absolute error doesn't exceed 10-2.


-----Constraints and subtasks-----
- 1 ≤ T ≤ 105
- 0 ≤ p ≤  1  
Subtask 1 (15 points) : 
1 ≤ M ≤ 3
Subtask 2 (55 points) : 
1 ≤ M ≤  103
Subtask 3 (30 points) : 
1 ≤ M ≤ 109

-----Example-----
Input:
2
1 0.5
2 0.5
Output:
1000000000.0 0.0
500000000.0 500000000.0

-----Explanation-----
Example case 1. In the second case, if decision isn't made at t = 0, total amount of money decreases to 5*108 at t = 1 which leads to a situation worse than the given solution.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
def divide(m, r):
	if r == 1:
		if m % 2 == 0:
			return 0.0
		else:
			return 1000000000.0
	n1 = int(m / 2) + m % 2
	n2 = m - n1
	c_sum = 10 ** 9 * ((r * r) ** n1 - 1) / (r * r - 1)
	if n2 > 0:
		o_sum = 10 ** 9 * r * ((r * r) ** n2 - 1) / (r * r - 1)
	else:
		o_sum = 0
	return c_sum - o_sum
t = int(input().strip())
while t > 0:
	(m, p) = input().strip().split()
	m = int(m.strip())
	p = float(p.strip())
	chef_share = divide(m, p)
	print(chef_share, 10 ** 9 - chef_share)
	t -= 1


T = int(input())
for i in range(0, T):
	inps = input()
	inps = inps.split()
	M = int(inps[0])
	P = float(inps[1])
	chef = 1000000000.0
	other = 0
	if M % 2 == 0:
		chef = chef * (1 - P ** M) / (P + 1.0)
		other = 1000000000.0 * (P * (1 + P ** (M - 1))) / (1 + P)
	else:
		chef = chef * (1 + P ** M) / (P + 1.0)
		other = 1000000000.0 * (P * (1 - P ** (M - 1))) / (1 + P)
	print(str(chef) + ' ' + str(other))


testCases = int(input())
while testCases > 0:
	numbers = input().split()
	M = int(numbers[0])
	p = float(numbers[1])
	a = 1000000000 * ((1 - (-p) ** M) / (1 + p))
	b = 1000000000.0 - a
	print(a, ' ', b)
	testCases = testCases - 1


t9 = 10 ** 9 * 1.0
tc = int(input(''))
while tc > 0:
	tc -= 1
	s = input('').split(' ')
	M = int(s[0])
	p = float(s[1])
	mbc = t9 * ((1 - (-p) ** M) / (1 + p))
	mbo = t9 - mbc
	print(mbc, mbo)


def ans(p, n):
	x = 1 - pow(-1 * p, n)
	x = x / (1 + p)
	return x
test = int(input())
while test != 0:
	test -= 1
	(n, p) = map(float, input().split())
	n = int(n)
	t = pow(10.0, 9)
	x = t * ans(p, n)
	y = t - x
	print(x, y)


amt = 1000000000.0
t = int(input())
for _ in range(t):
	ans = 0.0
	temp = 1.0
	(n, p) = map(float, input().split())
	r = p ** 2
	n = int(n)
	if r != 1:
		if n % 2 == 0:
			ans += (1 - r ** (n / 2)) / (1 - r)
			ans -= p * (1 - r ** (n / 2)) / (1 - r)
		else:
			power = int(n / 2) + 1
			ans += (1 - r ** power) / (1 - r)
			ans -= p * (1 - r ** (power - 1)) / (1 - r)
		print(amt * ans, amt - amt * ans)
	elif n % 2 == 0:
		print(0.0, amt)
	else:
		print(amt, 0.0)


t = int(input())
for i in range(t):
	s = input().split()
	(m, p) = (int(s[0]), float(s[1]))
	if m % 2 == 0:
		r = (1 - p ** m) / (1 + p)
	else:
		r = (1 + p ** m) / (1 + p)
	print(1000000000 * r, 1000000000 * (1 - r))


def loot(m, p):
	value = 1 + pow(-1, m - 1) * pow(p, m)
	value = value / (1 + p)
	return 1000000000 * value
T = int(input())
for i in range(0, T):
	inp = input().split()
	m = int(inp[0])
	p = float(inp[1])
	print(loot(m, p), end=' ')
	print(1000000000.0 - loot(m, p))


t = int(input())
while t:
	s = input().split()
	m = int(s[0])
	p = float(s[1])
	if m % 2 == 0:
		r = (1 - p ** m) / (p + 1)
	else:
		r = (1 + p ** m) / (p + 1)
	print(1000000000 * r, 1000000000 * (1 - r))
	t -= 1


t = int(input())
while t > 0:
	l = input().split()
	m = int(l[0])
	p = float(l[1])
	c = 10 ** 9
	s = (1 - (-1 * p) ** m) / (1 + p)
	print('%f %f' % (c * s, c * (1 - s)))
	t -= 1


a = int(input())
while a > 0:
	a -= 1
	b1 = input()
	(m, p) = [float(n) for n in b1.split()]
	if m == 1 or p == 0:
		print('1000000000.0 0.0')
	elif p == 1 and m % 2 == 1:
		print('1000000000.0 0.0')
	elif p == 1 and m % 2 != 1:
		print('0.0 1000000000.0')
	elif m == 2 and p == 0.5:
		print('500000000.0 500000000.0')
	else:
		k = 1000000000.0
		s1 = (-p) ** m
		a1 = k * ((1.0 - s1) / (1.0 + p))
		a2 = k - a1
		print(a1, a2)


t = int(input())
while t > 0:
	(m, p) = map(float, input().strip().split())
	a2 = p * (1 - (-p) ** (m - 1)) / (1 + p)
	a1 = 1 - a2
	print('%f %f' % (a1 * 10 ** 9, a2 * 10 ** 9))
	t -= 1


t = int(input())
B = pow(10, 9)
for i in range(1, t + 1):
	x = input().split()
	m = int(x[0])
	p = float(x[1])
	a = B * (1 - pow(-1, m) * pow(p, m)) / (1 + p)
	print(a, B - a)


import math
from decimal import Decimal

def upp(x, n):
	if n == 1:
		return x
	if n == 0:
		return float(1.0)
	x2 = x
	t = 1
	while 2.0 * t < n:
		t *= 2.0
		x2 *= x2
		if x2 == 0:
			break
	if x2 == 0:
		return 0
	return x2 * upp(x, n - t)

def mult(s):
	l = len(s)
	ans = ''
	for i in range(2, 11):
		if i >= l:
			ans += '0'
		else:
			ans += s[i]
	ans2 = ''
	fail = 0
	for i in range(0, 9):
		if fail == 1:
			ans2 += ans[i]
		if ans[i] != '0' and fail == 0:
			ans2 += ans[i]
			fail = 1
	if len(ans2) == 0:
		ans2 += '0'
	ans2 += '.'
	i == 8
	while i < l:
		ans2 += s[i]
		i += 1
	ans2 += '0'
	return ans2
T = int(input())
for i in range(0, T):
	inp = input().split()
	m = int(inp[0])
	p = float(inp[1])
	B = float(1000000000)
	svar = (1.0 - upp(-p, m)) / (p + 1)
	svar2 = 1 - svar
	r = B * svar
	l = B * svar2
	print(str(r) + ' ' + str(l))


t = int(input())
while t > 0:
	(m, p) = [float(x) for x in input().split()]
	m = int(m)
	if m % 2 == 0:
		c = (1 - pow(p, m)) / (1 + p)
	else:
		c = (1 + pow(p, m)) / (1 + p)
	r = c * 10 ** 9
	print(str(r) + ' ' + str(10 ** 9 - r))
	t = t - 1


for _ in range(int(input())):
	(m, p) = map(float, input().split())
	ans = 10 ** 9 * (1 - (-p) ** m) / (1 + p)
	print(ans, 10 ** 9 - ans)


loot = 1000000000.0
T = int(input())
while T != 0:
	inpline = input().split()
	M = int(inpline[0])
	p = float(inpline[1])
	frac = 0
	if p == 0:
		print(loot, 0)
	else:
		frac = (1 + pow(p, M) * pow(-1, M - 1)) / (1 + p)
		chef = loot * frac
		col = loot * (1 - frac)
		print(chef, col)
	T -= 1


bank = 10 ** 9
for t in range(int(input())):
	line = input().split()
	(m, p) = (int(line[0]), float(line[1]))
	if m == 1:
		print(bank, 0)
	else:
		c = bank * (1 - (-1 * p) ** m) / (1 + p)
		og = bank - c
		print(c, og)


import math, sys
t = int(input())
while t > 0:
	(m, p) = map(float, sys.stdin.readline().split())
	sum1 = 1000000000 * (1 - pow(-p, m)) / (1 + p)
	print(str(float(sum1)) + ' ' + str(float(1000000000 - sum1)))
	t = t - 1


t = int(input())
for i in range(t):
	line = input().split()
	m = int(line[0])
	p = float(line[1])
	tmp1 = (1 - (-p) ** m) / (1 + p)
	tmp2 = 1 - tmp1
	a = 1000000000 * tmp1
	b = 1000000000 * tmp2
	print(str(a) + ' ' + str(b))


cur = pow(10, 9)
for _ in range(int(input())):
	(p, q) = map(float, input().split())
	x = cur * (1 - pow(-q, p)) / float(1 + q)
	y = cur - x
	print(x, y)


t = int(input())
while t:
	t = t - 1
	(m, p) = input().split()
	m = int(m)
	p = float(p)
	x = 1000000000.0 * (1 - (-p) ** m) / (1 + p)
	print(x, end=' ')
	print(1000000000.0 - x)


import decimal

def share_money(money, p, t):
	if t == 1:
		return [money, 0.0]
	else:
		share1 = 0
		sign = 1
		for index in range(t):
			share1 += sign * pow(p, index)
			sign *= -1
		share1 *= money
	share2 = money - share1
	return [share1, share2]

def share_money2(money, p, t):
	if t == 1:
		return [money, 0.0]
	share1 = money * ((1 - pow(-p, t)) / (1 + p))
	share2 = money - share1
	return [share1, share2]
money = float(pow(10, 9))
t = int(input())
for case in range(t):
	(M, p) = list(map(float, input().split()))
	M = int(M)
	(share1, share2) = share_money2(money, p, M)
	answer = '{} {}'.format(share1, share2)
	print(answer)


for i in range(0, int(input())):
	(m, p) = input().split()
	m = int(m)
	p = float(p)
	val = (1 + (-1) ** (m % 2 + 1) * pow(p, m)) / (p + 1)
	print('%.2f %.2f' % (1000000000 * val, 1000000000 * (1 - val)))


T = int(input())
for t in range(T):
	x = input().split()
	m = int(x[0])
	p = float(x[1])
	y = p ** m
	if m % 2 == 0:
		y = -y
	x = 1000000000 * (1 + y) / (1 + p)
	print(x, 1000000000 - x)


billion = pow(10, 9)

def geometricSum(a, q, n):
	assert q != 1
	return a * (1 - pow(q, n)) / (1 - q)

def bestDivision(t, p):
	if t == 1 or p == 0:
		return (billion, 0)
	if p == 1:
		if t % 2 != 0:
			return (billion, 0)
		else:
			return (0, billion)
	chiefMoneyNext = billion * geometricSum(1, -p, t)
	return (chiefMoneyNext, billion - chiefMoneyNext)
tc = int(input())
while tc > 0:
	inputWords = input().split()
	(t, p) = (int(inputWords[0]), float(inputWords[1]))
	result = bestDivision(int(t), p)
	print(result[0], result[1])
	tc -= 1


t = int(input())
b = 1000000000.0
for i in range(t):
	s = input().split()
	m = int(s[0])
	p = float(s[1])
	y = b * p
	x = b - y
	if m == 1:
		print('%.3f %.3f' % (b, 0.0))
	else:
		if m % 2 == 0:
			x = b * (1 - p ** m) / (1 + p)
			y = b - x
		else:
			x = b * (1 + p ** m) / (1 + p)
			y = b - x
		print('%.3f %.3f' % (x, y))


import time
import sys
billion = pow(10, 9)
maxT = pow(10, 5)
maxM = pow(10, 9)

def geometricSum(a, q, n):
	assert q != 1
	return a * (1 - pow(q, n)) / (1 - q)

def bestDivision(t, p):
	if t == 1 or p == 0:
		return (billion, 0)
	if int(p) == 1:
		if t % 2 != 0:
			return (billion, 0)
		else:
			return (0, billion)
	chiefMoneyNext = billion * geometricSum(1.0, -p, t)
	return (chiefMoneyNext, billion - chiefMoneyNext)
tc = int(input())
while tc > 0:
	inputWords = input().split()
	(t, p) = (int(inputWords[0]), float(inputWords[1]))
	result = bestDivision(int(t), p)
	print(result[0], result[1])
	tc -= 1


t = int(input())
M = 1000000000
while t:
	t -= 1
	(a, b) = list(map(float, input().split(' ')))
	y = pow(b, a - 1)
	if a % 2 == 0:
		ans = b * M * (1 + y) / (b + 1)
	else:
		ans = b * M * (1 - y) / (b + 1)
	c = M - ans
	print(c, ans)


import math
M = 1000000000
for _ in range(0, int(input())):
	(t, p) = map(float, input().split())
	t = int(t)
	if t % 2 == 1:
		A = M * (p ** t + 1) / (p + 1)
	else:
		A = M * (1 - p ** t) / (p + 1)
	print('%.4f %.4f' % (A, M - A))


import math
t = int(input())
Bil = 1000000000
while t:
	a = [float(x) for x in input().split()]
	m = int(a[0])
	p = a[1]
	temp = math.pow(p, m)
	if m % 2 is 0:
		temp = 1 - temp
	else:
		temp += 1
	temp /= 1 + p
	temp *= Bil
	print(temp, ' ', Bil - temp)
	t -= 1


T = int(input())
for t in range(T):
	(M, p) = [x for x in input().split()]
	M = int(M)
	p = float(p)
	val = (pow(-p, M) - 1) / (-p - 1) * 10 ** 9
	print(val, 10 ** 9 - val)


tc = int(input())
while tc:
	(m, p) = input().split(' ')
	m = int(m)
	p = float(p)
	sum = (1 - (-p) ** m) / (1 + p)
	print(1000000000 * sum, ' ', 1000000000 * (1 - sum))
	tc -= 1


Booty = 1000000000.0
T = int(input())
while T != 0:
	inpline = input().split()
	M = int(inpline[0])
	p = float(inpline[1])
	f = 0
	if p == 0:
		print(Booty, 0)
	else:
		f = (1 + pow(p, M) * pow(-1, M - 1)) / (1 + p)
		chef = Booty * f
		coleg = Booty * (1 - f)
		print(chef, coleg)
	T -= 1


T = int(input())
billion = 1000000000.0
for t in range(T):
	tokens = input().split()
	M = int(tokens[0])
	p = float(tokens[1])
	chef = (1 - pow(-p, M)) / (1 + p) * billion
	print(chef, billion - chef)