USACO for Canadian students

Sample input:
5 2 10
1 2 3 15 31

Sample output:
40

# Brute force for checking: try every sailing in turn
import sys
data = sys.stdin.read().split()
n, cap, gap = int(data[0]), int(data[1]), int(data[2])
arrive = [int(x) for x in data[3:3 + n]]
i, depart = 0, 0
while i < n:
    depart += gap
    boarded = 0
    while i < n and boarded < cap and arrive[i] <= depart:
        i += 1
        boarded += 1
print(depart)

Correct, and fine for the sample. But it visits every sailing, and with arrival times up to a billion and T as small as 1, that can mean a billion empty sailings. On a contest grader it would pass the small tests and time out on the large ones.

# Our Bronze-style practice problem: Ferry Queue (not a USACO problem)
import sys

def main():
    data = sys.stdin.read().split()
    n, cap, gap = int(data[0]), int(data[1]), int(data[2])
    arrive = [int(x) for x in data[3:3 + n]]   # already in order
    i = 0
    depart = 0
    while i < n:
        # next sailing: the one after the last, or the first one
        # at or after the next car's arrival, whichever is later
        first_for_car = -(-arrive[i] // gap) * gap   # ceiling to a multiple
        depart = max(depart + gap, first_for_car)
        boarded = 0
        while i < n and boarded < cap and arrive[i] <= depart:
            i += 1
            boarded += 1
    print(depart)

main()

The idea: empty sailings change nothing, so jump straight to the next sailing that matters, either the one after the last, or the first one at or after the next car's arrival, found by rounding up to a multiple of T. Each car is handled once, so the work grows with N, not with the times. In the sample, cars at 1 and 2 leave at 10, cars at 3 and 15 at 20, and the car at 31 at 40. The equal-time rule, arrival ≤ departure, is the detail most first attempts get wrong.