|
Интересная эстафета
(Время: 2 сек. Память: 32 Мб Сложность: 35%)
Сегодня трудно удивить телезрителей известными видами спорта. Организаторы одного из зимних соревнований решили провести лыжную эстафету в новом формате: лыжники бегут не друг за другом, а друг навстречу другу.
Есть две команды, в каждой по N лыжников. Первая команда стартует из пункта A, вторая – из пункта B (назовём их командой A и командой B соответственно), находящихся на одной прямой на расстоянии D друг от друга. Участники эстафеты двигаются навстречу друг другу в противоположный пункт. Пусть лыжники пронумерованы от 1 до 2N, причём лыжники с нечётными номерами стартуют из пункта A, а лыжники с чётными номерами – из пункта B. Так как это очень подготовленные участники, будем считать, что все они движутся с одинаковой скоростью, равной 1. Для добавления интриги каждому из них назначили случайное время старта Ti так, что внутри одной команды лыжники с меньшими номерами стартуют раньше лыжников с большими номерами, то есть верно, что T1 < T3 < T5 < ... < T2N-1 и T2 < T4 < T6 < ... < T2N. Кроме того, выполняется условие T1 ≤ T2 , то есть первый из команды A стартует не позже первого из команды B.
Первый лыжник из команды A стартует с эстафетным флажком. Далее происходит следующее: лыжник, двигающийся с флажком, передаёт его первому встречному спортсмену из противоположной команды (если таковой имеется). Тот поступает точно так же. Это происходит до тех пор, пока кто-то из лыжников с флагом не прибежит в точку старта противоположной команды, не встретив ни одного соперника по пути, и тем самым не одержит победу. Телезрителей же волнует следующий вопрос: какое расстояние преодолеет флаг, прежде чем один из лыжников принесёт его в точку старта соперников?
Входные данные
В первой строке входного файла INPUT.TXT находится целое число N – количество лыжников в каждой команде (1 ≤ N ≤ 105).
Во второй строке находится целое число D – расстояние между пунктами A и B (1 ≤ D ≤ 109).
В следующих N строках содержатся времена Ti старта лыжников из команды A (0 ≤ T1 < T3 < T5 < ... < T2N-1 ≤ 109).
В следующих N строках содержатся времена Ti старта лыжников из команды B (0 ≤ T2 < T4 < T6 < ... < T2N ≤ 109).
Гарантируется, что T1 ≤ T2.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – расстояние, которое преодолеет эстафетный флаг, прежде чем один из лыжников принесёт его в противоположный пункт. Обратите внимание на то, что если флаг принесут в один из пунктов в тот момент, когда из этого пункта стартует очередной лыжник, – это считается победой, эстафета окончена.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
5
0
3
7
8
14
2
3
11
13
20 | 13 |
| 2 | 6
10
5
6
7
8
9
10
14
15
16
17
18
19 | 24 |
Пояснение к первому примеру
В каждой команде по 5 лыжников (N = 5). Расстояние между пунктами равно 5 (D = 5), для дальнейших рассуждений предположим, что пункт A находится в точке 0, а пункт B – в точке 5. Лыжники команды A стартуют в моменты 0, 3, 7, 8, 14. Лыжники команды
B стартуют в моменты 2, 3, 11, 13, 20. События следуют так:
- момент 0 – старт лыжника 1 с флагом из пункта A;
- момент 2 – старт лыжника 2 из пункта B;
- момент 3 – старт лыжника 3 из пункта A и лыжника 4 из пункта B;
- момент 3.5 – лыжники 1 и 2 встретятся в точке 3.5, флаг окажется у лыжника 2 (флаг сместился вправо на 3.5);
- момент 5 – лыжники 3 и 2 встретятся в точке 2, флаг окажется у лыжника 3 (флаг сместился влево на 1.5);
- момент 5.5 – лыжники 3 и 4 встретятся в точке 2.5, флаг окажется у лыжника 4 (флаг сместился вправо на 0.5);
- момент 7 – старт лыжника 5 из пункта A;
- момент 7.5 – лыжники 5 и 4 встретятся в точке 0.5, флаг окажется у лыжника 5 (флаг сместился влево на 2);
- момент 8 – старт лыжника 7 из пункта A;
- момент 11 – старт лыжника 6 из пункта B;
- момент 11.5 – лыжники 5 и 6 встретятся в точке 4.5, флаг окажется у лыжника 6 (флаг сместился вправо на 4);
- момент 12 – лыжники 7 и 6 встретятся в точке 4, флаг окажется у лыжника 7 (флаг сместился влево на 0.5);
- момент 13 – старт лыжника 8 из пункта B, но лыжник 7 в этот момент прибежит с флагом в пункт B, и команда А победит (флаг сместился вправо на 1).
В итоге флаг проделал путь длиной 3.5+1.5+0.5+2+4+0.5+1 = 13.
Система оценки
Решения, правильно работающие при N ≤ 1000, будут оцениваться в 40 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
