#Generating quasi-random RNA with Theta = 1
#Process: choose random mate for node 1; recurse on "inside" and "outside"
#Compute the expected number of basepairs


# D. Krizanc

from random import *
def qr(n):
    if n==0: return 0
    if n==1: return 0
    if n==2: return 0
    if n==3: return 1
    if n==4: return 1
    k = randint(1,n-2)
    return 1+qr(k)+qr(n-k-2)

n = 1000
trials = 10000
total = 0.0
for i in range(trials):
    total = total + qr(n)
print n, trials, total/(n*trials)