p826

p826.py

import random, fractions

def monte_carlo(trials, n):
    total = 0
    for _ in range(trials):
        painted = 0
        pts = sorted([random.random() for _ in range(n)])
        prev = 1
        for i, x in enumerate(pts):
            if i == 0:
                painted += pts[i + 1] - x
            elif i == (n - 1):
                if prev == 0:
                    painted += x - pts[i - 1]
            else:
                v = [x - pts[i - 1], pts[i + 1] - x]
                if v[1] > v[0]:
                    curr = 0
                else:
                    curr = 1
                if prev != 1 or curr != 0:
                    painted += v[curr]
                prev = curr
        total += painted
    return n, total/trials, fractions.Fraction(total / trials).limit_denominator(1000), fractions.Fraction(total / trials).limit_denominator(100)