// RUN: @caesar @file --function-encoding fuel-param --quantifier-instantiation e-matching

domain Harmonic {
    func harmonic(n: UInt): UReal = ite(n == 0, 0, harmonic(n - 1) + 1 / n)
}

@ert
coproc coupon_collector(N: UInt) -> ()
    pre !?(N > 0)
    pre N * harmonic(N)
    post 0
{
    var x: UInt = N
    // The expected number of remaining draws is at most N * harmonic(x).
    // The condition x <= N keeps x / N within [0,1].
    @invariant(!?(x <= N) ⊔ N * harmonic(x))
    while x > 0 {
        var found_new: Bool = false
        // The expected wait for the next new coupon is N / x draws.
        // The expected number of later draws is at most N * harmonic(x - 1).
        @invariant(ite(found_new, 0, N / x) + N * harmonic(x - 1))
        while !found_new {
            tick 1
            found_new = flip(x / N)
        }
        x = x - 1
    }
}
