Problem 3: Airplane Boarding [Travis Hance]

FJ's cows have decided to take a vacation, and have miraculously managed to find an airline willing to sell them tickets. When they arrive at the airport and start boarding their plane, they face an interesting problem, however.

The airplane has N seats, which we model as the points x=1 through x=N on the number line. All N cows (1 <= N <= 200,000) are standing in line waiting to get to their seats. Cow N is at position x=0, Cow N-1 is at position x=-1, and so on. Cow i has been assigned to Seat S_i, where S_1,...,S_N is a permutation of 1,...,N.

At each time step, each cow takes a step to the right if she can. When cow i reaches her seat S_i, she will stop to put her baggage in the overhead bin, which takes T_i seconds, and then sit down. For those T_i steps, the cow behind her (if there is one) is blocked from moving forward. If there is a line of cows behind her, the line is effectively blocked as well.

How long will it take for all the cows to sit down?

The sum of T_i for all cows will be less than 1,000,000,000.

PROBLEM NAME: boarding

#3874 upload 1 done 1 how_to_reg 1

Airplane Boarding timer 1s memory 128MB

#3874

Airplane Boarding 1s 128MB