Matrix Exponentiation

Recursion. It's true if the list is empty or when pivoting as described, one of the sublists is empty and the recursive call is true.

def solve(N, A):
    if N == 0: return True
    j = (len(A) - 1) // 2
    B, C, P = [], [], A[j]
    for i, x in enumerate(A):
        if i == j: continue
        (B if x <= P else C).append(x)

    if B and C: return False
    return solve(N-1, B or C)

Because we can excuse or ignore teams, we can choose any subset of the teams in any order. Also, if we are to beat a team, we should beat the weakest one; and if we are to recruit a team, we should recruit the strongest one. Thus our strategy is going to take the form of: "Defeat teams until we can't, then recruit a team" and we will repeat this.

def solve(E, N, A):    
    A.sort()
    ans = honor = 0
    while A:
        while A and E > A[0]:
            E -= A.pop(0)
            honor += 1
        if honor == 0: break
        ans = max(ans, honor)
        if A:
            honor -= 1
            E += A.pop()

    return ans

First, use Floyd's algorithm to find dist[i][j] (0 indexed). Now, notice that if you are not home, you are in every other location with equal probability. If you are at home (location 0) then the expected travel time to your destination is sum(dist[0]) / (N-1). If you are away (ie., not at home), then the expected travel time to your destination is sum(dist[1:]) / (N-1)^2. Also, we can figure out the transition function: if you are home with probability x, then on the next monster you are home with probability (1-x)/(N-1).

To solve the problem for large, you need one extra fact. For the function f(x) = (1-x)/(N-1), getting within 1e-9 of the limit of the orbit lim_{i ->inf} f^i(1) = 1/N is done very quickly. Indeed, let's look at abs(x — f(x)) = abs(Nx — 1)/(N-1), suggesting f^i(1) -> 1/N. To prove it, abs(f(x) — f(f(x))) = abs(Nf(x) — 1)/(N-1) = abs(N(1-x) — (N-1))/(N-1)^2 = abs(Nx — 1)/(N-1)^2. So the differences are getting smaller by a factor of 1/(N-1) each time.

def solve(N, M, P, A):
    dist = [[float('inf')] * N for _ in xrange(N)]
    for u, v, w in A:
        u -= 1; v -= 1
        dist[u][v] = dist[v][u] = w
        dist[u][u] = dist[v][v] = 0
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                d = dist[i][k] + dist[k][j]
                if dist[i][j] > d: dist[i][j] = d

    val_home = sum(dist[0]) / float(N - 1)
    val_away = sum(sum(row) for row in dist[1:]) / float((N-1)**2)
    
    ans = 0
    home = 1.0
    MAGIC = 200
    for _ in xrange(min(MAGIC, P)):
        delta = val_home * home + val_away * (1.0 - home)
        ans += delta
        home = (1.0 - home) / float(N-1)

    return ans + delta * max(0, P - MAGIC)

Straightforward DP.

_issq = lambda N: int(N**.5) ** 2 == N
issq = map(_issq, range(10001))

memo = {0: 0}
def solve(N):
    if N not in memo:
        ans = 4
        for x in xrange(1, N+1):
            if issq[x]:
                ans = min(ans, 1 + solve(N-x))
        memo[N] = ans
    return memo[N]

map(solve, range(10000))