Little Elephant from the Zoo of Lviv hates exams. Since Little Elephant lives in Ukraine, he is going to take exams called 'ZNO'. Help him.
There will be n tickets on the table. Each ticket has a number written on it. The i-th ticket can be numbered A_{i} with probability P_{i} percent and with probability 100-P_{i} percent it can be numbered B_{i}. It can not have any other number. A numbering of tickets on the table is correct if and only if all tickets have distinct ticket numbers.

Help Little Elephant find the probability that the numbering will be correct.

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

The first line of the input contains a single integer T - the number of test cases. T test cases follow. The first line of each test case contains a single integer n - the number of tickets on the table. n lines will follow. Each of these lines contains three integers: P_{i},  A_{i} and B_{i}.

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

Output T lines, each containing a single real number - answer for the corresponding test case. Rounding errors less than 10^{-6} will be ignored.

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

1 ≤ T ≤ 10

1 ≤ n ≤ 50

1 ≤ A_{i}, B_{i} ≤ 16

0 ≤ P_{i} ≤ 100

----- Sample Input 1 ------ 
2
2
50 1 2
50 2 1
3
100 1 3
47 2 1
74 3 2
----- Sample Output 1 ------ 
0.500000000
0.347800000

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Probability
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
MAX_N = 16

def produce_ints():
	for line in sys.stdin:
		for word in line.split():
			yield int(word)

def next_int():
	return next(produce_ints())

def test(x, bit):
	return x >> bit & 1

def one_test():
	n = next_int()
	a = tuple((tuple(map(int, input().split())) for i in range(n)))
	if n > MAX_N:
		return 0
	dp = {0: 1.0}
	for (pr, a, b) in a:
		pr_a = 0.01 * pr
		pr_b = 1 - pr_a
		a -= 1
		b -= 1
		next_dp = {}
		for (mask, prob) in dp.items():
			if not test(mask, a):
				next_mask = mask | 1 << a
				next_dp[next_mask] = next_dp.get(next_mask, 0) + prob * pr_a
			if not test(mask, b):
				next_mask = mask | 1 << b
				next_dp[next_mask] = next_dp.get(next_mask, 0) + prob * pr_b
		dp = next_dp
	return sum(dp.values())
t = next_int()
for i in range(t):
	print('{:.7f}'.format(one_test()))


def prob(x, pi, st):
	return 0 if st[16 - x] == '1' else pi

def solve(n, st, a, b, p, dp):
	if n == 0:
		dp[n][st] = 1.0
	elif st not in dp[n]:
		pa = prob(a[n - 1], p[n - 1], st)
		ast = ''.join(('1' if i == 16 - a[n - 1] else st[i] for i in range(16)))
		dp = solve(n - 1, ast, a, b, p, dp)
		pa *= dp[n - 1][ast]
		pb = prob(b[n - 1], 1 - p[n - 1], st)
		bst = ''.join(('1' if i == 16 - b[n - 1] else st[i] for i in range(16)))
		dp = solve(n - 1, bst, a, b, p, dp)
		pb *= dp[n - 1][bst]
		dp[n][st] = pa + pb
	return dp
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	(a, b, p) = ([], [], [])
	for i in range(n):
		(pi, ai, bi) = map(int, input().strip().split())
		a.append(ai)
		b.append(bi)
		p.append(pi / 100)
	DP = [{} for i in range(n + 1)]
	st = '0' * 16
	dp = solve(n, st, a, b, p, DP)
	print(dp[n][st])


def explore(progress, tickets, result_p):
	if len(progress) is len(tickets):
		result_p.append(progress[-1][1])
		return
	ticket = tickets[len(progress)]
	(p, a, b) = (ticket[0] / 100, ticket[1], ticket[2])
	prev_p = 1 if len(progress) is 0 else progress[-1][1]
	if a not in [x[0] for x in progress]:
		progress.append([a, p * prev_p])
		explore(progress, tickets, result_p)
		progress.pop()
	if b not in [x[0] for x in progress]:
		progress.append([b, (1 - p) * prev_p])
		explore(progress, tickets, result_p)
		progress.pop()
t = int(input())
for _ in range(t):
	n = int(input())
	if n > 16:
		[input() for x in range(n)]
		print('%.9f' % 0.0)
	else:
		tickets = [[int(y) for y in input().split()] for x in range(n)]
		result_p = []
		explore([], tickets, result_p)
		print('%.9f' % sum(result_p))


def solve(i, used, prob):
	if i == n:
		return prob
	ans = 0.0
	for (l, pp) in [(a[i], p[i]), (b[i], 100 - p[i])]:
		if used[l - 1] == True:
			continue
		used[l - 1] = True
		ans += solve(i + 1, used, prob * pp / 100)
		used[l - 1] = False
	return ans
cases = int(input())
while cases:
	cases -= 1
	a = []
	p = []
	b = []
	n = int(input())
	for i in range(n):
		(a1, a2, a3) = map(int, input().split())
		p.append(a1)
		a.append(a2)
		b.append(a3)
	if n > 16:
		print(0)
		continue
	lab = [False] * 16
	print(solve(0, lab, 1.0))


P = [0.0] * 51
A = [0] * 51
B = [0] * 51
lst = [0] * 51

def cal_pro(row):
	i = int(row)
	if i > n - 1:
		return 1
	if (P[i] == 1 or A[i] == B[i]) and lst[A[i]] == 0:
		lst[A[i]] += 1
		temp1 = cal_pro(i + 1)
		lst[A[i]] -= 1
		return temp1
	elif P[i] == 0 and lst[B[i]] == 0:
		lst[B[i]] += 1
		temp2 = cal_pro(i + 1)
		lst[B[i]] -= 1
		return temp2
	else:
		if lst[A[i]] == 0:
			lst[A[i]] += 1
			temp1 = P[i] * cal_pro(i + 1)
			lst[A[i]] -= 1
		else:
			temp1 = 0
		if lst[B[i]] == 0:
			lst[B[i]] += 1
			temp2 = (1 - P[i]) * cal_pro(i + 1)
			lst[B[i]] -= 1
		else:
			temp2 = 0
		return temp1 + temp2
T = int(input())
while T:
	T -= 1
	n = int(input())
	for i in range(0, n):
		str = input().split()
		P[i] = float(str[0]) / 100.0
		A[i] = int(str[1])
		B[i] = int(str[2])
		ans = 0.0
		ans = cal_pro(0)
	print('%.6f' % ans)


import copy
for _ in range(int(input())):
	dp = [[1, {}]]
	val = []
	n = int(input())
	for i in range(n):
		(p, a, b) = map(int, input().split())
		val.append((p / 100, a, b))
	for i in range(len(val)):
		ndp = []
		for j in range(len(dp)):
			if dp[j][0] == 0:
				continue
			if val[i][1] not in dp[j][1].keys():
				x = {}
				x = copy.deepcopy(dp[j][1])
				x[val[i][1]] = 0
				ndp.append([dp[j][0] * val[i][0], x])
			if val[i][2] not in dp[j][1].keys():
				x = {}
				x = copy.deepcopy(dp[j][1])
				x[val[i][2]] = 0
				ndp.append([dp[j][0] * (1 - val[i][0]), x])
		dp = ndp
	ans = 0
	for val in dp:
		ans += val[0]
	print(ans)


import sys

def Prob(Taken, i):
	if i == N[0]:
		return 1
	if (Taken, i) not in Mem:
		if A[i] in Taken:
			x = 0
		else:
			x = Prob(tuple(sorted(Taken + (A[i],))), i + 1) * (P[i] / 100)
		if B[i] in Taken:
			y = 0
		else:
			y = Prob(tuple(sorted(Taken + (B[i],))), i + 1) * ((100 - P[i]) / 100)
		Mem[Taken, i] = x + y
	return Mem[Taken, i]
T = int(sys.stdin.readline())
Ans = ''
for t in range(T):
	Mem = {}
	N = [int(sys.stdin.readline())]
	(A, B, P) = ([], [], [])
	for i in range(N[0]):
		(p, a, b) = map(int, sys.stdin.readline().split())
		P.append(p)
		A.append(a)
		B.append(b)
	Ans += str(Prob((), 0)) + '\n'
sys.stdout.write(Ans)


def mk(i, u, pr):
	if i == n:
		return pr
	else:
		t = 0.0
		for (l, pp) in [(a[i], p1[i]), (b[i], 100 - p1[i])]:
			if u[l - 1] == True:
				continue
			u[l - 1] = True
			t += mk(i + 1, u, pr * pp / 100)
			u[l - 1] = False
	return t
t = int(input())
for i in range(t):
	a = []
	p1 = []
	b = []
	n = int(input())
	for i in range(n):
		(a1, a2, a3) = map(int, input().split())
		p1.append(a1)
		a.append(a2)
		b.append(a3)
	if n > 16:
		print(0)
		continue
	lab = [False] * 16
	x = str(mk(0, lab, 1.0))
	x = x.split('.')
	temp = 9 - len(x[1])
	for j in range(temp):
		x[1] += '0'
	print('.'.join(x))


def bit2int(bits):
	return int(''.join(map(str, bits)), 2)

def int2bit(n):
	binary = bin(n)[2:]
	binary = '0' * (16 - len(binary)) + binary
	return list(map(int, binary))

def prob(x, pi, st):
	return 0 if st[16 - x] == '1' else pi

def solve(n, st, a, b, p, dp):
	if n == 0:
		dp[n][st] = 1.0
	elif st not in dp[n]:
		pa = prob(a[n - 1], p[n - 1], st)
		ast = ''.join(('1' if i == 16 - a[n - 1] else st[i] for i in range(16)))
		(ares, dp) = solve(n - 1, ast, a, b, p, dp)
		pa *= ares
		pb = prob(b[n - 1], 1 - p[n - 1], st)
		bst = ''.join(('1' if i == 16 - b[n - 1] else st[i] for i in range(16)))
		(bres, dp) = solve(n - 1, bst, a, b, p, dp)
		pb *= bres
		dp[n][st] = pa + pb
	return (dp[n][st], dp)
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	(a, b, p) = ([], [], [])
	for i in range(n):
		(pi, ai, bi) = map(int, input().strip().split())
		a.append(ai)
		b.append(bi)
		p.append(pi / 100)
	DP = [{} for i in range(n + 1)]
	st = '0' * 16
	(res, dp) = solve(n, st, a, b, p, DP)
	print(res)


import sys
import math

def find_prob(bolean, arr, ans, idx):
	if idx == len(arr):
		return ans
	(prob, a, b) = arr[idx]
	(x, y) = (0, 0)
	if not bolean[a]:
		bolean[a] = True
		x = find_prob(bolean, arr, ans * prob / 100, idx + 1)
		bolean[a] = False
	if not bolean[b]:
		bolean[b] = True
		y = find_prob(bolean, arr, ans * (1 - prob / 100), idx + 1)
		bolean[b] = False
	if bolean[a] and bolean[b]:
		return 0
	return x + y

def main(arr):
	ans = 1
	boolean = [False] * 17
	print(find_prob(boolean, arr, ans, 0))
for _ in range(int(input())):
	arr = []
	for j in range(int(input())):
		arr.append(list(map(int, input().split())))
	main(arr)