Read problems statements in Mandarin Chinese and Russian as well. 

Petr, Nikita G. and Nikita are the most influential music critics in Saint-Petersburg. They have recently downloaded their favorite band's new album and going to listen to it. Nikita claims that the songs of entire album should be listened strictly in the same order as they are given, because there is the secret message from the author in the songs' order. Petr, being chaotic, does not think so, hence he loves listening to songs in a random order. Petr is pretty good in convincing other people, so after a two-hours discussion Nikita accepted listening in random order(the discussion's duration was like three times longer thatn the album's one). In this context random order means following: There are N songs in the album. In the very beginning random song is chosen(here and further "random song" means that every song has equal probability to be chosen). After some song is over the next one is chosen randomly and independently of what have been played before. 

Nikita G., being the only one who is not going to drop out from the university, wonders, what is the expected number of songs guys have to listen to until every song is played at least once. 

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

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. 

The first and only line of each test case contains a single integer N denoting the number of songs in the album. 

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

For each test case, output a single line containing the expected number of songs the guys will listen to. Your answer will be considered as correct if it has an absolute or relative error less than 10^{−1}. More formally if the expected output is A and your output is B, your output will be considered as correct if and only if
|A − B| ≤ 10^{−1} * max{|A|, |B|, 1}.

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

1 ≤ T ≤  100 
1 ≤ N ≤  3000 
 
----- Sample Input 1 ------ 
3
1
2
3
----- Sample Output 1 ------ 
1.0
3.0
5.5

------ Explanation 0 ------ 

Example case 2 After playing the first song there is 1/2 chance to finish the album each time new song is played. So the expected number of songs is 2/2 + 3/4 + 4/8... = 3

Difficulty: HARD
Tags: Dynamic programming

Mathematics

Probability
Skill types: Dynamic programming

Starter code:

Solutions:
T = int(input())

def prob(N):
	return sum([N / x for x in range(1, N + 1)])
for _ in range(0, T):
	N = int(input())
	print(prob(N))


for t in range(int(input())):
	n = int(input())
	total = 0
	for i in range(1, n + 1):
		total += n / i
	print(total)


t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	for i in range(n):
		ans += 1 / (i + 1)
	print(ans * n)


t = int(input())
for ti in range(t):
	n = int(input())
	print(sum((n / i for i in range(1, n + 1))))


a = [0, 1]
dif = 1
for i in range(1, 3030):
	dif += 1.0 / i
	a.append(a[-1] + dif)
for i in range(int(input())):
	print(a[int(input())])


for tests in range(int(input())):
	m = int(input())
	print(sum([(m - n) / (m * (n / m - 1) ** 2) for n in range(0, m)]))


t = int(input())
for loop in range(0, t):
	a = int(input())
	z = 0
	for i in range(0, a):
		z = z + a / (a - i)
	print(z)


t = int(input())
while t >= 0:
	try:
		n = int(input())
		t = t - 1
	except:
		break
	a = 0
	for j in range(1, n + 1):
		a += float(1 / j)
	print(a * n)


test = int(input())
for x in range(test):
	n = float(input())
	print(sum([n / j for j in range(1, int(n + 1))]))


array = [0 for x in range(3000)]
array[0] = 1
for k in range(1, 3000):
	array[k] = array[k - 1] + 1 / (k + 1)
for q in range(int(input())):
	num = int(input())
	print(num * array[num - 1])


for _ in range(int(input())):
	n = int(input())
	k = n
	sum = 0
	for i in range(1, n + 1):
		sum += 1 / i
	sum = sum * n
	print(round(sum, 1))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	H = 0.0
	for i in range(1, n + 1):
		H += 1.0 * n / i
	print(H)


for _ in range(int(input())):
	n = int(input())
	ans = n * sum([1 / i for i in range(1, n + 1)])
	print('{:.6}'.format(ans))


test = eval(input())
while test:
	n = eval(input())
	sum = 0
	for i in range(n):
		sum += n / (i + 1)
	print(sum)
	test = test - 1


test = int(input())
for _ in range(test):
	b = int(input())
	a = 0
	for j in range(1, b + 1):
		a += float(1 / j)
	print(a * b)


for t in range(int(input())):
	n = int(input())
	b = 0
	for j in range(1, n + 1):
		b += float(1 / j)
	print(b * n)


from itertools import *
from math import *

def binomial(n, k):
	return factorial(n) // factorial(k) // factorial(n - k)
memo = dict()

def f(n, d):
	if tuple([n, d]) in memo:
		return memo[tuple([n, d])]
	if n == 1:
		memo[tuple([n, d])] = 1
		return 1
	if n == d:
		memo[tuple([n, d])] = factorial(n)
		return factorial(n)
	if d < n:
		memo[tuple([n, d])] = 0
		return 0
	memo[tuple([n, d])] = n ** d - n * f(n - 1, d)
	return n ** d - n * f(n - 1, d)
log_fac = [0, 0]
for i in range(2, 3333):
	log_fac.append(log_fac[-1] + log(i))
memo2 = dict()

def g(n, d):
	x = tuple([n, d])
	if x in memo2:
		return memo2[x]
	if n == 1:
		return 0
	if n == d:
		return log_fac[n]
	if d < n:
		return -999999999999999999999999999999999999
	return log((1.0 * n) ** d - n * exp(g(n - 1, d)))

def main():
	T = int(input())
	for t in range(T):
		n = int(input())
		ans = 0
		for i in range(1, n + 1):
			ans += 1 / i
		ans *= n
		print(ans)
	return
	for n in range(1, 11):
		a = []
		for d in range(1, 16):
			a.append(f(n, d))
	for n in range(1, 11):
		b = []
		for d in range(1, 16):
			b.append(factorial(n) * n ** (d - n))
	print(1, 1)
	for n in range(2, 3001):
		ans = 0
		for d in range(n, 200):
			ans += d * (1 / n) ** d * f(n - 1, d - 1)
		print(n, n * ans)
main()


t = int(input())
output = []
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
		continue
	count = 0
	for i in range(n, 0, -1):
		count += 1 / i
	print(count * n)


t = int(input())
for _ in range(t):
	n = int(input())
	sum = 0
	for j in range(1, n + 1):
		sum += float(1 / j)
	print(sum * n)


import sys
tc = int(input())
for i in range(tc):
	n = int(input())
	sum = 0
	for i in range(1, n + 1):
		sum = sum + 1 / i
	ev = sum * n
	print(round(ev, 1))


n = int(input())
for i in range(n):
	m = int(input())
	sum = 0
	for j in range(1, m + 1):
		sum = sum + m / j
	print(sum)


t = int(input())
for v in range(t):
	n = int(input())
	summ = 0
	for i in range(n):
		summ += 1 / (i + 1)
	summ = summ * n
	print(summ)


for i in range(int(input())):
	n = int(input())
	l = [1 / (i / n) for i in range(1, n + 1)]
	print(sum(l))


result = []
test = int(input())
for i in range(0, test):
	n = int(input())
	sumA = 1
	tmp = n - 1
	while tmp > 0:
		sumA = float(sumA) + float(n / float(tmp))
		tmp = tmp - 1
	result.append(sumA)
for i in range(0, len(result)):
	print(result[i])


n = int(input())
for _ in range(n):
	k = int(input())
	s = float(k)
	for i in range(1, k):
		x = float(i) / float(k)
		s += x / (1.0 - x)
	print(s)


for _ in range(int(input())):
	n = int(input())
	b = 0
	for i in range(1, n + 1):
		b += 1 / i
	b *= n
	print(b)


test = int(input())
for j in range(test):
	m = int(input())
	final = 1
	for i in range(m - 1):
		final += m / (i + 1)
	print(final)


t = int(input())
for i in range(t):
	n = int(input())
	tns = 1.0
	for i in range(1, n):
		tns = n / i + tns
	print(tns)


x = int(input())

def expect(num):
	prob = 0
	for i in range(1, num + 1):
		prob = prob + float(1 / i)
	val = prob * num
	return val
for t in range(x):
	n = int(input())
	print(expect(n))


arr = [0] * 3001
arr[1] = 1
for i in range(2, 3001):
	arr[i] = arr[i - 1] + 1 / i
for _ in range(int(input())):
	n = int(input())
	print(n * arr[n])


T = int(input())

def expect(n):
	val = 0
	for i in range(1, n + 1):
		val += float(1 / i)
	val *= n
	return val
for t in range(T):
	N = int(input())
	print(expect(N))


from math import ceil, sqrt, log, gcd
from collections import deque, defaultdict as dd
from os import path
import sys
t = int(input())
for f in range(t):
	n = int(input())
	tt = 0
	for i in range(n, 0, -1):
		tt = tt + n / i
	print(tt)


a = int(input())
for i in range(a):
	b = int(input())
	s = 0
	for j in range(1, b + 1):
		s = s + b / j
	print(s)


for vishal in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(1, n + 1):
		ans += 1 / i
	ans *= n
	print(ans)


for _ in range(int(input())):
	n = int(input())
	lista = list((1 / (i / n) for i in range(1, n + 1)))
	print(sum(lista))


a = int(input())
for _ in range(a):
	b = int(input())
	sum = 0
	for i in range(1, b + 1):
		sum += b / i
	print(sum)


import sys
import math

def main(n):
	ans = 1
	for i in range(1, n):
		ans += n / (n - i)
	return ans
t = int(input())
for i in range(t):
	print(main(int(input())))


def average_takes(num):
	prob = 1
	for i in range(num - 1, 0, -1):
		prob += float(num) / float(i)
	return prob
ABC = int(input())
Arr = []
for i in range(ABC):
	Arr.append(int(input()))
for i in Arr:
	print(average_takes(i))


for _ in range(int(input())):
	n = int(input())
	p = 0
	for i in range(1, n + 1):
		p += n / i
	print(p)


for i in range(int(input())):
	n = int(input())
	a = 0
	for j in range(1, n + 1):
		a += float(1 / j)
	print(a * n)


t = int(input())
for i in range(t):
	n = int(input())
	ans = 0
	prob = 0
	for j in range(1, n + 1):
		prob += 1 / j
	ans += prob * n
	print(ans)


for t in range(int(input())):
	n = int(input())
	k = 1.0
	for i in range(1, n):
		k = k + n / (n - i)
	print(k)


for _ in range(int(input())):
	n = int(input())
	m = 0
	for i in range(1, n + 1):
		m += n / i
	print(m)


x = int(input())
for i in range(x):
	m = int(input())
	final = 1
	for i in range(m - 1):
		final += m / (i + 1)
	print(final)


for tc in range(int(input())):
	n = int(input())
	print(n * sum((1 / x for x in range(1, n + 1))))


tests = int(input())
result = []
while tests > 0:
	num = int(input())
	temp = num
	tests = tests - 1
	s1 = 0
	while temp >= 1:
		s1 = s1 + 1 / temp
		temp = temp - 1
	result.append(num * s1)
for a in result:
	print(a)


for _ in range(int(input())):
	n = int(input())
	a = 0
	for i in range(1, n + 1):
		a += n / i
	print('%.1f' % a)


answers = []
for _ in range(int(input())):
	n = int(input())
	answers.append(n * sum(list(map(lambda x: 1 / x, range(1, n + 1)))))
print(*answers, sep='\n')