"""Rate min_y [log2(1+y) - log2 W(y)/n] of RS-theta (generating-function form, exact up to the
polynomial factor n+1 by Remark rem:gf) for stars of stars and paths with m pendants per solution
vertex.  G[S] = F and pendant outside vertices, so Lemma E is an equality.  Float, rescaled."""
import math
def init(y, m): return [y / 2, 0.0, 2.0 ** (-m)]
def mrg(P, Q):
    A, B, C = P; a, b, c = Q
    return [A * (2 * a + b + c), B * (a + b + c / 2) + C * a, C * (b + c / 2)]
def logW_star(s, m, y):
    P = init(y, m); lg = 0.0; leaf = init(y, m)
    for _ in range(s - 1):
        P = mrg(P, leaf); sc = max(P); P = [x / sc for x in P]; lg += math.log2(sc)
    return lg + math.log2(P[0] + P[1] + P[2] / 2)
def logW_path(s, m, y):
    P = init(y, m); lg = 0.0
    for _ in range(s - 1):
        P = mrg(init(y, m), P); sc = max(P); P = [x / sc for x in P]; lg += math.log2(sc)
    return lg + math.log2(P[0] + P[1] + P[2] / 2)
def rate(f, s, m):
    n = s * (m + 1)
    g = lambda y: math.log2(1 + y) - f(s, m, y) / n
    lo, hi = 1e-4, 20.0
    for _ in range(200):
        a, b = lo + (hi - lo) / 3, hi - (hi - lo) / 3
        if g(a) < g(b): hi = b
        else: lo = a
    return g((lo + hi) / 2), (lo + hi) / 2
for name, f in (('star of stars', logW_star), ('path', logW_path)):
    best = max((rate(f, 2000, m)[0], m) for m in range(0, 9))
    print(name, ' '.join(f"m={m}:{2 ** rate(f, 2000, m)[0]:.5f}" for m in range(0, 9)), ' max base', f"{2 ** best[0]:.5f}", 'at m =', best[1])