ВОП ЦДРО 8 класс: Заключительный этап, день 2

В робомарафоне принимают участие n роботов. Роботы должны преодолеть одинаковую дистанцию, передвигаясь по расположенным рядом друг с другом дорожкам шириной один метр каждая. Известно, что расположенный на i -й дорожке робот преодолевает дистанцию за a _i секунд.

В точке старта каждого робота установлено специальное сигнальное устройство, которое должно сработать в момент старта. Чтобы сделать соревнования менее предсказуемыми, судьи перед стартом могут отключить некоторые сигнальные устройства, остальные устройства останутся активными . Только активные устройства срабатывают в тот момент, когда главный судья начинает робомарафон. В начале робомарафона хотя бы одно сигнальное устройство должно являться активным.

Каждый робот начинает движение в тот момент, когда до него доходит стартовый сигнал от активного устройства. Сигнал распространяется со скоростью 1 метр в секунду. Расстояние между дорожками i и j равно | i - j | метров. Обозначим как x _i расстояние от i -й дорожки до ближайшей дорожки, содержащей активное устройство. Робот на i -й дорожке начнёт движение через x _i секунд после старта, преодолеет дистанцию за a _i секунд, и финиширует через f _i = a _i + x _i секунд после старта робомарафона.

Пусть k _i — количество роботов, которые финишировали строго раньше i -го робота. Место i -го робота по итогам робомарафона равно k _i + 1 . Если несколько роботов финишируют одновременно, а перед ними финишировали k роботов, то считается, что все они заняли ( k + 1) -е место.

Рассмотрим пример. Пусть n = 3 , роботы преодолевают дистанцию за a ₁ = 2 , a ₂ = 3 и a ₃ = 5 секунд, а активным являлось только сигнальное устройство у третьего робота. Тогда первый робот начнёт движение через 2 секунды после начала забега, f ₁ = 4 . Второй робот начнёт движение через 1 секунду, f ₂ = 4 . Третий робот начнёт движение в момент старта, f ₃ = 5 . По итогам забега первый и второй робот делят первое место, третий робот занимает третье место. Если же, например, сработают все три сигнальных устройства, роботы финишируют через f ₁ = 2 , f ₂ = 3 , f ₃ = 5 , секунд, соответственно. Первый робот займёт первое место, второй робот займёт второе место, а третий робот — третье место.

Как видно из примера, место, которое займёт робот, зависит от того, какие сигнальные устройства являются активными. Необходимо обрабатывать два типа запросов:

• для каждого робота определить минимальное место, которое он может занять;
• для каждого робота определить максимальное место, которое он может занять.

Требуется написать программу, которая по типу запроса и информации о времени прохождения дистанции каждым роботом определяет для каждого робота минимальное или максимальное место, которое он может занять в робомарафоне.