Alex enjoys performing magic tricks. He has a trick that requires a deck of n cards. He has m identical decks of n different cards each, which have been mixed together. When Alex wishes to perform the trick, he grabs n cards at random and performs the trick with those. The resulting deck looks like a normal deck, but may have duplicates of some cards.

The trick itself is performed as follows: first Alex allows you to choose a random card from the deck. You memorize the card and put it back in the deck. Then Alex shuffles the deck, and pulls out a card. If the card matches the one you memorized, the trick is successful.

You don't think Alex is a very good magician, and that he just pulls a card randomly from the deck. Determine the probability of the trick being successful if this is the case.


-----Input-----

First line of the input consists of two integers n and m (1 ≤ n, m ≤ 1000), separated by space — number of cards in each deck, and number of decks.


-----Output-----

On the only line of the output print one floating point number – probability of Alex successfully performing the trick. Relative or absolute error of your answer should not be higher than 10^{ - 6}.


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

Output
0.6666666666666666

Input
4 4

Output
0.4000000000000000

Input
1 2

Output
1.0000000000000000



-----Note-----

In the first sample, with probability $\frac{1}{3}$ Alex will perform the trick with two cards with the same value from two different decks. In this case the trick is guaranteed to succeed.

With the remaining $\frac{2}{3}$ probability he took two different cards, and the probability of pulling off the trick is $\frac{1}{2}$.

The resulting probability is $\frac{1}{3} \times 1 + \frac{2}{3} \times \frac{1}{2} = \frac{2}{3}$

Difficulty: HARD
Tags: Combinatorics

Mathematics

Probability

Starter code:

Solutions:
var = input('')
var = var.split(' ')
x = int(var[0])
y = int(var[1])
if x == 1 and y == 1:
	print('1')
else:
	p1 = (y - 1) / (x * y - 1)
	p2 = (1 - p1) * (1 / x)
	print(p1 + p2)


import sys
(n, m) = list(map(int, sys.stdin.read().split()))
if m * n == 1:
	print(1)
else:
	print(1 - m * (n - 1) ** 2 / ((m * n - 1) * n))


def main():
	(n, m) = list(map(int, input().split()))
	if n == 1 == m:
		res = 1.0
	else:
		res = (2 * n * m - n - m) / (n * m - 1) / n
	print('{:.16f}'.format(res))

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
if 1 == n:
	print(1)
else:
	print(1 / n + (n - 1) * (m - 1) / (n * (n * m - 1)))


import collections
import math

def readLine():
	return list(map(int, input().strip().split()))

def readInt():
	return int(input())

def readString():
	return input()

def tcase():
	t = readInt()
	for _ in range(t):
		solve()

def solve():
	(n, m) = readLine()
	f = [0] * (n * m + 1)
	for i in range(2, n * m + 1):
		f[i] = f[i - 1] + math.log(i)

	def c(n, k):
		return f[n] - f[k] - f[n - k]
	ans = 0
	for num in range(1, min(n, m) + 1):
		temp = c(m, num) + c(m * (n - 1), n - num) - c(m * n, n)
		pro = num * num * 1.0 / (n * 1.0)
		ans += pro * math.pow(math.e, temp)
	print(ans)
solve()


from math import *
logger = []
for n in range(1000111):
	if n == 0:
		logger.append(log(factorial(0)))
	else:
		logger.append(logger[n - 1] + log(n))

def binomial(n, k):
	if k < 0:
		return 0
	tmp = logger[n] - logger[k] - logger[n - k]
	return tmp

def main():
	(n, m) = [int(x) for x in input().split()]
	ans = 0
	for i in range(n):
		tmp = binomial((n - 1) * m, n - 1 - i) + binomial(m - 1, i) + log(i + 1)
		tmp -= log(n) + binomial(n * m - 1, n - 1)
		ans += exp(tmp)
	print('%.12lf' % ans)
main()


(n, m) = list(map(int, input().split()))
print(1.0 if n == m == 1 else 1 / n * ((n - 1) * (m - 1) / (n * m - 1) + 1))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
if n == 1:
	print(1)
else:
	print((2 * m * n - m - n) / (n * (n * m - 1)))


F = [1, 1]
for i in range(2, 1001):
	F.append(F[-1] * i)

def ncr(x, y):
	return F[x] // (F[y] * F[x - y])
(n, m) = list(map(int, input().split()))
P = [0] * 2000
for j in range(1, min(m, n) + 1):
	mine = m
	total = n * m
	p = 1
	for x in range(j):
		p *= mine / total
		mine -= 1
		total -= 1
	for x in range(n - j):
		p *= (total - mine) / total
		total -= 1
	p *= n
	p *= ncr(n, j)
	P[j] = p
ans = 0
for j in range(1, min(m, n) + 1):
	p = P[j]
	ans += P[j] * (j * j) / (n * n)
print(ans)


def solve():
	from sys import stdin
	line = stdin.readline
	(n, m) = map(int, line().split())
	if n == m == 1:
		print(1.0)
		return
	p = 1 / n + (n - 1) / n * (m - 1) / (n * m - 1)
	print(p)
	return
solve()


(n, m) = map(int, input().split())
if n == 1:
	print(1)
else:
	print('{:9}'.format((n - 1) / n * (m - 1) / (n * m - 1) + 1 / n))


def cal(m, n, i):
	tot = 1
	for j in range(1, n - i + 1):
		tot = tot * (n * m - m - n + i + j) / (n * m - n + i + j)
	for j in range(1, i + 1):
		tot = tot * (m - i + j) / (n * m - n + j)
	for j in range(1, i + 1):
		tot = tot / j * (n - i + j)
	return tot
(n, m) = input().split()
n = int(n)
m = int(m)
ans = 0
for i in range(1, min(n, m) + 1):
	ans += i * i / n * cal(m, n, i)
print(ans)


(n, m, ans) = map(int, input().split() + [0])
f = [1] * 1005
for i in range(1, 1005):
	f[i] = i * f[i - 1]
for i in range(1, 1 + min(n, m)):
	t = f[n] // (f[i] * f[n - i])
	for j in range(i):
		t *= (m - j) / (n * m - j)
	for j in range(n - i):
		v = n * m - i - j
		t *= (v - m + i) / v
	ans += t * i * i / n
print(ans)


import itertools
import math
S = 1000000
fact = list(itertools.accumulate(range(S + 1), lambda x, y: x + math.log(y)))
(n, m) = [int(x) for x in input().split()]
res = 0.0
for i in range(1, min(n, m) + 1):
	res += math.exp(math.log(n) + (fact[m] - fact[i] - fact[m - i]) + (fact[(n - 1) * m] - fact[n - i] - fact[(n - 1) * m - n + i]) - (fact[n * m] - fact[n] - fact[n * m - n]) + math.log((1.0 * i / n) ** 2))
print(res)


S = str(input())
l = list(map(int, S.split(' ')))
(n, m) = (l[0], l[1])
S = 0
t = 1 / n
l = m * n - m - n
y = min(n, m)
z = max(n, m)
for i in range(1, y + 1):
	if i > 1:
		t = t * i * (m + 1 - i) * (m * n - z - i + 2) * (n + 1 - i) / ((i - 1) * (i - 1) * (l + i) * (n * m - i + 1))
	S = S * (m * n - z - i + 2) / (n * m - i + 1) + t
print(S)


import sys
import os
(n, m) = map(float, sys.stdin.readline().split())
res = 0
if n == 1:
	res = 1
else:
	res = (1 + (n - 1) * (m - 1) / (n * m - 1)) / n
print(res)


(n, m) = map(int, input().split())
t = m * n
print(1 if t == 1 else (2 * t - (m + n)) / (n * (t - 1)))


(n, m) = (int(x) for x in input().split(' '))
if n != 1 or m != 1:
	print(1 / n + (n - 1) / n * (m - 1) / (m * n - 1))
else:
	print(1)


(n, m) = list(map(int, input().split()))
print('{:.9}'.format((1 + (n - 1) * (m - 1) / (n * m - 1)) / n if n > 1 or m > 1 else 1.0))


(n, m) = map(float, input().split())
if n == 1:
	print(1)
else:
	print((1 + (n - 1) * (m - 1) / (n * m - 1)) / n)


import math
import decimal
import functools

@functools.lru_cache(maxsize=None)
def factorial(n):
	return math.factorial(n)

@functools.lru_cache(maxsize=None)
def binomial(k, n):
	if k > n // 2:
		return product(range(k + 1, n + 1)) / factorial(n - k)
	else:
		return product(range(n - k + 1, n + 1)) / factorial(k)

def P(k, n, m):
	return k ** 2 / n * binomial(k, n) * product(((m - i) / (m * n - i) for i in range(k))) * product(((m * n - i - (m - k)) / (m * n - i) for i in range(k, n)))

def product(iterable):
	res = 1
	for e in iterable:
		res *= e
	return res

def solve(n, m):
	return sum((P(k, n, m) for k in range(1, min(n, m) + 1)))
(n, m) = map(int, input().split())
print(solve(n, m))


def process(n, m):
	if n * m == 1:
		return 1
	a = (n - 1) * (m - 1) / (n * m - 1)
	return (a + 1) / n
(n, m) = [int(x) for x in input().split()]
print(process(n, m))


from decimal import *
import sys
getcontext().prec = 100
(n, m) = input().split()
n = eval(n)
m = eval(m)
if n * m <= 2:
	if n == 2 and m == 1:
		print(0.5)
	else:
		print(1)
	sys.exit()
n = Decimal(n)
m = Decimal(m)
a = m * n
b = n - 1
b = b * b
ans = (a - 1 + (n - 1) * (m - 1)) / (n * (a - 1))
print(ans)