Олимпиадный тренинг

Задача . Airplane Boarding


Задача

Темы: Задачи на моделирование
Problem 3: Airplane Boarding [Travis Hance]
Коровы прибыли в в аэропорт и столкнулись с интересной проблемой.
В самолёте имеется N мест, которые мы моделируем как точки от x=1 до x=N на числовой прямой. Все N коров (1 <= N <= 200,000) стоят в ряд, ожидая занятия своего места. Корова N стоит на позиции x=0, корова N-1 на позиции x=-1 и т.д. Корове I назначено место Si, где S1, S2, … - это перестановка чисел от 1 до N.
Каждую секунду каждая корова делает шаг вправо, если она может. Когда корова I достигает своего места Si, она останавливается, чтобы положить багаж в верхний отсек салона, это занимает у неё Ti секунд, затем она садится. В течение этих Ti секунд, следующая за этой корова (если она есть) блокируется и не может двигаться вперёд. Если за ней вплотную стоят коровы, то они тоже все блокируются.
Сколько времени займёт посадка?
Сумма всех Ti будет меньше чем 1,000,000,000.
PROBLEM NAME: boarding
Формат входных данных
* Строка 1: Одно целое число, N.
* Lines 2..N+1: Два разделённых пробелом целых числа, Si и Ti.
Формат выходных данных
* Строка 1: Одно целое число, задающее количество времени, которое потребуется, чтобы все коровы заняли свои места.
Примечание
После первой секунды, все сдвинутся на 1 вправо и корова 3 достигнет своего места:
123 123
Корове 3 потребуется 5 секунд, чтобы сесть, после чего она «исчезает».
12 123
Потребуется еще 3 секунды коровам 1 и 2 чтобы добраться до своих мест:
12 123
Корове 1 потребуется 5 секунд, чтобы сесть, корове 2 – 10, поэтому ВСЕ усядутся через 10 секунд.
Общее время посадки: 1 + 5 + 3 + 10 = 19 секунд
Примеры
№Входные данныеВыходные данные
1 
3
2 5
3 10
1 5
 
19
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет