Solution 1

For this solution, the idea is to first assign as many missed shots as possible to each player's free misses, since they do not contribute to the penalty. Note that ~f[i] > N~ is possible, and in this case, the player can only take ~N~ free misses, not ~f[i]~. Any remaining misses must then be distributed among the players, and the penalty for a player is the number of extra misses they receive beyond their free misses. To minimize the maximum penalty ~L~, we assign at most one extra miss to each player in each round, repeating until all remaining misses are accounted for. We assign at most one extra missed shot to each player in each round to ensure the extra missed shots are distributed as evenly as possible. Keep in mind that we must be careful not to assign more than ~N~ missed shots to any player, which is why we should keep track of the number of missed shots we have already assigned to each player (including the free misses). The total number of rounds required to account for all remaining misses is exactly the minimum value of ~L~.

N, M, T = map(int, input().split())
f = list(map(int, input().split()))

cnt = 0
capacity = [0] * M

for i in range(M):
    cnt += min(N, f[i])
    capacity[i] = max(0, N - f[i])

extra = T - cnt
penalty = 0

while extra > 0:
    for i in range(M):
        if extra <= 0:
            break
        if capacity[i] > 0:
            extra -= 1
            capacity[i] -= 1
    penalty += 1

print(penalty)

Time Complexity: ~\mathcal{O}(NM)~

Solution 2

A simpler solution is to iterate over the possible values of ~L~. This represents the maximum penalty, which we know must be between ~0~ and ~N~. To ensure that the maximum penalty does not exceed ~L~, each player can be assigned at most ~f[i]+L~ missed shots. Once again, note that if ~f[i]+L > N~, we take the number of missed shots for that player to be ~N~. So, we can sum up the maximum number of missed shots we can assign to each player. If that sum is greater than or equal to ~T~, we have found a solution for ~L~. Thus, we can just loop ~L~ from ~0~ up to ~N~, to ensure that the first solution for ~L~ that works is also the minimum value for ~L~.

N, M, T = map(int, input().split())
f = list(map(int, input().split()))

for L in range(N + 1):
    max_missed = sum(min(L + misses, N) for misses in f)
    if max_missed >= T:
        print(L)
        break

Time Complexity: ~\mathcal{O}(NM)~