The Bad Luck Island is inhabited by three kinds of species: r rocks, s scissors and p papers. At some moments of time two random individuals meet (all pairs of individuals can meet equiprobably), and if they belong to different species, then one individual kills the other one: a rock kills scissors, scissors kill paper, and paper kills a rock. Your task is to determine for each species what is the probability that this species will be the only one to inhabit this island after a long enough period of time.


-----Input-----

The single line contains three integers r, s and p (1 ≤ r, s, p ≤ 100) — the original number of individuals in the species of rock, scissors and paper, respectively.


-----Output-----

Print three space-separated real numbers: the probabilities, at which the rocks, the scissors and the paper will be the only surviving species, respectively. The answer will be considered correct if the relative or absolute error of each number doesn't exceed 10^{ - 9}.


-----Examples-----
Input
2 2 2

Output
0.333333333333 0.333333333333 0.333333333333

Input
2 1 2

Output
0.150000000000 0.300000000000 0.550000000000

Input
1 1 3

Output
0.057142857143 0.657142857143 0.285714285714

Difficulty: HARD
Tags: Dynamic programming

Probability
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
input = sys.stdin.readline
(r, s, p) = map(int, input().split())
dp = [[[0] * (p + 1) for i in range(s + 1)] for j in range(r + 1)]
dp[r][s][p] = 1
for i in range(r + 1)[::-1]:
	for j in range(s + 1)[::-1]:
		for k in range(p + 1)[::-1]:
			x = i * j + j * k + k * i
			if i > 0 and j > 0:
				dp[i][j - 1][k] += i * j * dp[i][j][k] / x
			if j > 0 and k > 0:
				dp[i][j][k - 1] += j * k * dp[i][j][k] / x
			if k > 0 and i > 0:
				dp[i - 1][j][k] += i * k * dp[i][j][k] / x
(a1, a2, a3) = (0, 0, 0)
for i in range(1, r + 1):
	a1 += dp[i][0][0]
for i in range(1, s + 1):
	a2 += dp[0][i][0]
for i in range(1, p + 1):
	a3 += dp[0][0][i]
print(a1, a2, a3)


(r, s, p) = [int(x) for x in input().split()]
dp = [[[0 for i in range(105)] for j in range(105)] for k in range(105)]
dp[r][s][p] = 1
for i in range(r, -1, -1):
	for j in range(s, -1, -1):
		for k in range(p, -1, -1):
			dnr = i * j + j * k + i * k
			if i > 0 and j > 0:
				dp[i][j - 1][k] += i * j * dp[i][j][k] / dnr
			if j > 0 and k > 0:
				dp[i][j][k - 1] += j * k * dp[i][j][k] / dnr
			if k > 0 and i > 0:
				dp[i - 1][j][k] += k * i * dp[i][j][k] / dnr
(roc, sci, pap) = [0] * 3
for i in range(105):
	roc += dp[i][0][0]
	sci += dp[0][i][0]
	pap += dp[0][0][i]
print(roc, sci, pap)


dp = [[[-1] * 105 for _ in range(105)] for __ in range(105)]
dp2 = [[[-1] * 105 for _ in range(105)] for __ in range(105)]
dp3 = [[[-1] * 105 for _ in range(105)] for __ in range(105)]

def f(x, y, z):
	if dp[x][y][z] != -1:
		return dp[x][y][z]
	if x == 0:
		return 0
	if y == 0:
		return 1
	if z == 0:
		return 0
	sumx = x * y + y * z + x * z
	dp[x][y][z] = x * y / sumx * f(x - 1, y, z) + y * z / sumx * f(x, y - 1, z) + x * z / sumx * f(x, y, z - 1)
	return dp[x][y][z]

def f2(x, y, z):
	if dp2[x][y][z] != -1:
		return dp2[x][y][z]
	if x == 0:
		return 1
	if y == 0:
		return 0
	if z == 0:
		return 0
	sumx = x * y + y * z + x * z
	dp2[x][y][z] = x * y / sumx * f2(x - 1, y, z) + y * z / sumx * f2(x, y - 1, z) + x * z / sumx * f2(x, y, z - 1)
	return dp2[x][y][z]

def f3(x, y, z):
	if dp3[x][y][z] != -1:
		return dp3[x][y][z]
	if x == 0:
		return 0
	if y == 0:
		return 0
	if z == 0:
		return 1
	sumx = x * y + y * z + x * z
	dp3[x][y][z] = x * y / sumx * f3(x - 1, y, z) + y * z / sumx * f3(x, y - 1, z) + x * z / sumx * f3(x, y, z - 1)
	return dp3[x][y][z]
(x, y, z) = map(int, input().split(' '))
print(f(x, z, y), f2(x, z, y), f3(x, z, y))


(r, s, p) = map(int, input().split())
memo = [[[-1] * 101 for _ in range(101)] for _ in range(101)]

def f(n):
	return n * (n - 1) // 2

def dfs(r, s, p):
	if memo[r][s][p] > -0.5:
		return memo[r][s][p]
	n = r + s + p
	if r == 0:
		memo[r][s][p] = 0.0
		return memo[r][s][p]
	if s == 0 and p == 0:
		memo[r][s][p] = 1.0
		return memo[r][s][p]
	ans = 0.0
	d = 1 - f(r) / f(n) - f(s) / f(n) - f(p) / f(n)
	if r > 0 and s > 0:
		ans += r * s / f(n) * dfs(r, s - 1, p)
	if s > 0 and p > 0:
		ans += s * p / f(n) * dfs(r, s, p - 1)
	if p > 0 and r > 0:
		ans += p * r / f(n) * dfs(r - 1, s, p)
	memo[r][s][p] = ans / d
	return memo[r][s][p]
print(dfs(r, s, p), dfs(s, p, r), dfs(p, r, s))


(r, s, p) = map(int, input().split())
dp = [[[0 for i in range(p + 1)] for j in range(s + 1)] for k in range(r + 1)]
dp[r][s][p] = 1
ro = r
while ro >= 0:
	si = s
	while si >= 0:
		pa = p
		while pa >= 0:
			val1 = ro * si
			val2 = pa * si
			val3 = pa * ro
			su = val1 + val2 + val3
			if su != 0:
				if ro >= 1:
					dp[ro - 1][si][pa] += val3 / su * dp[ro][si][pa]
				if pa >= 1:
					dp[ro][si - 1][pa] += val1 / su * dp[ro][si][pa]
				if si >= 1:
					dp[ro][si][pa - 1] += val2 / su * dp[ro][si][pa]
			pa += -1
		si += -1
	ro += -1
p1 = 0
p2 = 0
p3 = 0
for i in range(1, r + 1):
	p1 += dp[i][0][0]
for i in range(1, s + 1):
	p2 += dp[0][i][0]
for i in range(1, p + 1):
	p3 += dp[0][0][i]
print(1 - p2 - p3, p2, p3)


[r, s, p] = list(map(float, input().split()))

def prob(k, n, b, mem):
	if k > 0 and n >= 0 and (b == 0):
		return ([1.0, 0.0, 0.0], mem)
	elif k == 0 and n > 0 and (b >= 0):
		return ([0.0, 1.0, 0.0], mem)
	elif k >= 0 and n == 0 and (b > 0):
		return ([0.0, 0.0, 1.0], mem)
	elif k < 0 or n < 0 or b < 0:
		return ([0.0, 0.0, 0.0], mem)
	elif k == n and k == b and (k > 0):
		return ([1.0 / 3.0, 1.0 / 3.0, 1.0 / 3.0], mem)
	elif not mem[int(k)][int(n)][int(b)] == None:
		l = mem[int(k)][int(n)][int(b)]
		return (l, mem)
	else:
		if mem[int(k - 1)][int(n)][int(b)] == None:
			(g0, mem) = prob(k - 1, n, b, mem)
		else:
			g0 = mem[int(k - 1)][int(n)][int(b)]
		if mem[int(k)][int(n - 1)][int(b)] == None:
			(g1, mem) = prob(k, n - 1, b, mem)
		else:
			g1 = mem[int(k)][int(n - 1)][int(b)]
		if mem[int(k)][int(n)][int(b - 1)] == None:
			(g2, mem) = prob(k, n, b - 1, mem)
		else:
			g2 = mem[int(k)][int(n)][int(b - 1)]
		l = []
		x = k * b
		y = k * n
		z = n * b
		r = x + y + z
		for i in range(3):
			l.append((x * g0[i] + y * g1[i] + z * g2[i]) / r)
		if k == 2.0 and n == 2.0 and (l == 1):
			print(mem[int(k)][int(n)][int(b)])
		mem[int(k)][int(n)][int(b)] = l
		if k == 2.0 and n == 2.0 and (l == 1):
			print(mem[int(k)][int(n)][int(b)])
		return (l, mem)
list_size = int(max([r, s, p])) + 1
mem = [None] * 120
for i in range(list_size):
	mem[i] = [None] * list_size
for i in range(list_size):
	for j in range(list_size):
		mem[i][j] = [None] * list_size
(s, x) = prob(r, s, p, mem)
for i in range(3):
	print(s[i], end=' ')


import sys
input = sys.stdin.readline

def I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, combinations, groupby
from operator import itemgetter
(rock, scissor, paper) = LI()
dp = [[[0 for p in range(paper + 1)] for s in range(scissor + 1)] for r in range(rock + 1)]
dp[rock][scissor][paper] = 1
for r in range(rock, -1, -1):
	for s in range(scissor, -1, -1):
		for p in range(paper, -1, -1):
			currsum = p * r + r * s + s * p
			if not currsum:
				continue
			if r >= 1:
				dp[r - 1][s][p] += p * r / currsum * dp[r][s][p]
			if s >= 1:
				dp[r][s - 1][p] += r * s / currsum * dp[r][s][p]
			if p >= 1:
				dp[r][s][p - 1] += s * p / currsum * dp[r][s][p]
pr = sum((dp[i][0][0] for i in range(1, rock + 1)))
ps = sum((dp[0][i][0] for i in range(1, scissor + 1)))
pp = sum((dp[0][0][i] for i in range(1, paper + 1)))
print(round(pr, 12), round(ps, 12), round(pp, 12))


(A, B, C) = map(lambda x: int(x) + 1, input().split())
M = max(max(A, B), C)
p = [[[0] * M for i in range(M)] for j in range(M)]
for a in range(M):
	for b in range(M):
		for c in range(M):
			val = 0
			if a == 0 or b == 0:
				val = 0
			elif c == 0:
				val = 1
			else:
				div = a * b + b * c + c * a
				val = a * b / div * p[a][b - 1][c] + b * c / div * p[a][b][c - 1] + a * c / div * p[a - 1][b][c]
			p[a][b][c] = val
print(p[A - 1][B - 1][C - 1], p[B - 1][C - 1][A - 1], p[C - 1][A - 1][B - 1])


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
(A, B, C) = mp()
A += 1
B += 1
C += 1
M = max(A, B, C)
p = [[[0] * M for i in range(M)] for j in range(M)]
for a in range(M):
	for b in range(M):
		for c in range(M):
			val = 0
			if a == 0 or b == 0:
				val = 0
			elif c == 0:
				val = 1
			else:
				div = a * b + b * c + c * a
				val = a * b / div * p[a][b - 1][c] + b * c / div * p[a][b][c - 1] + a * c / div * p[a - 1][b][c]
			p[a][b][c] = val
print(p[A - 1][B - 1][C - 1], p[B - 1][C - 1][A - 1], p[C - 1][A - 1][B - 1])


def read_data():
	(r, s, p) = map(int, input().split())
	return (r, s, p)

def P(r, s, p):
	global memo
	if memo[r][s][p]:
		return memo[r][s][p]
	if r == 0:
		return (0, 1, 0)
	if s == 0:
		return (0, 0, 1)
	if p == 0:
		return (1, 0, 0)
	rs = r * s
	rp = r * p
	sp = s * p
	denom = rs + rp + sp
	prs = rs / denom
	prp = rp / denom
	psp = sp / denom
	(r1, s1, p1) = P(r, s - 1, p)
	(r2, s2, p2) = P(r - 1, s, p)
	(r3, s3, p3) = P(r, s, p - 1)
	new_r = r1 * prs + r2 * prp + r3 * psp
	new_s = s1 * prs + s2 * prp + s3 * psp
	new_p = p1 * prs + p2 * prp + p3 * psp
	memo[r][s][p] = (new_r, new_s, new_p)
	memo[s][p][r] = (new_s, new_p, new_r)
	memo[p][r][s] = (new_p, new_r, new_s)
	return (new_r, new_s, new_p)
(r, s, p) = read_data()
memo = [[[False] * 101 for i in range(101)] for j in range(101)]
(pr, ps, pp) = P(r, s, p)
print('{:.12} {:.12} {:.12}'.format(pr, ps, pp))


(r, s, p) = list(map(int, input().split()))
dp = [[[0] * (p + 1) for _ in range(s + 1)] for _ in range(r + 1)]
dp[r][s][p] = 1

def nCk(n, k):
	if n <= k:
		return 1
	res = 1
	for i in range(k):
		res *= n - i
	for i in range(k):
		res //= i + 1
	return res
C = [nCk(i, 2) for i in range(r + s + p + 1)]
for ri in range(r, -1, -1):
	for si in range(s, -1, -1):
		for pi in range(p, -1, -1):
			t = ri * si + si * pi + pi * ri
			if t == 0:
				continue
			if ri > 0:
				dp[ri - 1][si][pi] += dp[ri][si][pi] * ri * pi / t
			if si > 0:
				dp[ri][si - 1][pi] += dp[ri][si][pi] * ri * si / t
			if pi > 0:
				dp[ri][si][pi - 1] += dp[ri][si][pi] * si * pi / t
r_sum = sum([dp[ri][0][0] for ri in range(r + 1)])
s_sum = sum([dp[0][si][0] for si in range(s + 1)])
p_sum = sum([dp[0][0][pi] for pi in range(p + 1)])
print(r_sum, s_sum, p_sum)


import os, sys
from io import BytesIO, IOBase

def main():
	(r, s, p) = map(int, input().split())
	dpr = [[[0] * (r + 1) for _ in range(s + 1)] for _ in range(p + 1)]
	for i in range(1, r + 1):
		dpr[0][0][i] = 1
	for i in range(p + 1):
		for j in range(s + 1):
			for k in range(r + 1):
				z = i * j + j * k + k * i
				if not z:
					continue
				dpr[i][j][k] = (dpr[i - 1][j][k] * i * j + dpr[i][j - 1][k] * j * k + dpr[i][j][k - 1] * i * k) / z
	dps = [[[0] * (r + 1) for _ in range(s + 1)] for _ in range(p + 1)]
	for i in range(1, s + 1):
		dps[0][i][0] = 1
	for i in range(p + 1):
		for j in range(s + 1):
			for k in range(r + 1):
				z = i * j + j * k + k * i
				if not z:
					continue
				dps[i][j][k] = (dps[i - 1][j][k] * i * j + dps[i][j - 1][k] * j * k + dps[i][j][k - 1] * i * k) / z
	print(dpr[-1][-1][-1], dps[-1][-1][-1], 1 - dpr[-1][-1][-1] - dps[-1][-1][-1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(r, s, p) = map(int, input().split())
n = 101
g = lambda i, j, k: i + n * (j + n * k)
t = [0] * n ** 3
for i in range(1, n):
	for j in range(n):
		for k in range(n):
			l = g(i, j, k)
			if j or k:
				(x, y, z) = (g(i, j - 1, k), g(i - 1, j, k), g(i, j, k - 1))
				(a, b, c) = (i * j, i * k, j * k)
				t[l] = (a * t[x] + b * t[y] + c * t[z]) / (a + b + c)
			else:
				t[l] = 1
(x, y, z) = (g(r, s, p), g(s, p, r), g(p, r, s))
print(t[x], t[y], t[z])


(r, s, p) = map(int, input().split())
n = 101
m = n * n
t = [0] * n * m
for i in range(1, n):
	for j in range(n):
		for k in range(n):
			d = i + n * j + m * k
			a = i * j * t[d - n] + i * k * t[d - 1] + j * k * t[d - m]
			b = i * j + i * k + j * k
			t[d] = a / b if j or k else 1
print(t[r + n * s + m * p], t[s + n * p + m * r], t[p + n * r + m * s])