Тима Рейзин

Зарегистрирован с 10.09.2019
Комментарии
18 января 2020

Чтоб легче было решать эту задачу, нужно нарисовать рисунок. Пускай расстоянием между джентельменами будет количество метров которые должен пройти один из них до другого по самому оптимальному пути. Тогда изначальное расстояние 1000м. Будем рассматривать моменты времени между интервалами времени за которые джентельмены проходят по 100м. Докажем что куда бы джентельмены не пошли в каждый такой момент времени расстояние между ними либо не изменится, либо уменьшится или увеличится на 200(но оно не будет бесконечно увеличиваться). «» Доказательство: Если джентельмен проходит по главной аллее вперёд то за один интервал времени(ну 100м от одного ответвления до другого) расстояние меняется на -100м, если сворачивает на ответвление то на +100м. Также и второй джентельмен. Если рассмотреть все случаи(100 + 100 = 200, 100 - 100 = 0, -100 - 100 = -200) то выходит что расстояние меняется либо на 200м, либо не меняется вообще. Что и требовалось доказать. «» Если независимо от ходов джентельменов за один интервал времени расстояние меняется на 200, либо на 0 и уменьшается в общем. То в конце концов расстояние между джентельменами будет 0. А значит джентельмены встретятся в любом случае. Ответ: Да, неизбежна.

Ответить
15 января 2020

Данную задачу модно решить с помощью дерева отрезков с обновлением на отрезке. Для каждого ученого будем пробавляться единицу на интервала рождение - смерть. Потом найдём максимум во всем массиве. Легко реализовать, чтоб при поиске максимума также возвращался интервал максимума. Что же к последнему предложению, то можно создать в массиве две ячейки - для начала и конца года, в каждую из которых соответственно можно записывать начала и конца жизней если они были в этом году. Ответом на задачу будет отрезок на котором находится максимум.

Ответить
BUG