Решение задачи 512

Условие:

На кольцевой дороге стоят n бензоколонок, в каждой какое-то количество бензина. Расстояния между бензоколонками известны. Имеется машина с постоянным и известным расходом топлива. При каких условиях можно стартовать с пустым баком из какой-то бензоколонки и проехать весь круг, заправляясь по пути?

Решение:

Будем считать, что длина дороги равна единице. Бензин в колонках будем измерять в длине дороги, которую можно проехать на этом бензине (например 0.2 бензина означает, что на нем можно проехать одну пятую всей дороги).

Если всего бензина во всех бензоколонках меньше единицы, то ответ на задачу отрицательный.

Покажем, что если всего бензина во всех бензоколонках не меньше единицы, то ответ всегда положительный.

Введем мощность колонки p_i -- разность количества бензина в этой колонке и расстояния до следующей колонки. Тогда сумма всех p_i не меньше нуля, ведь p+1 + .. + p_n = f_1 + .. f_n - 1, где f_i -- количество бензина в i-ой колонке.

Рассмотрим сумму s(k) = p_1 + ... + p_k (k < n), что она символизирует? Количество бензина, который у нас останется, если мы стартанем из первой колонки и доедем до k+1-ой, заправляясь во всех колонках по пути (кроме последней). Формально, бензин в любой момент может быть отрицательным, считаем, что всегда можем ехать. Рассмотрим все такие суммы s(1), s(2), ... s(n). Если все они неотрицательные, то мы без проблем можем проехать весь круг, стартовав в первой колонке. Напомним, что s(n) в рассматриваемой ситуации всегда не меньше нуля.

Если какие-то s(k) отрицательные, то рассмотрим минимальную из них, пусть это s(q), q < n. Покажем, что если стартовать в колонке q + 1, то можно проехать весь круг. Пусть мы это не смогли сделать, то есть доехали до какой-то колонки с отрицательным бензином: p(q+1) + ... + p(t) < 0, но тогда p(1) + .. + p(q) + p(q+1) + ... + p(t) < s(q). Сумма слева от знака может иметь больше n слагаемых (если бензин кончился после первой бензоколонки). Неравенство имеет вид либо s(t) < s(q) или s(t) + s(n) < s(q). В любом случае s(t) < s(q), противоречие с выбором минимального s(k).

Ответ: Если суммарного бензина во всех колонках не хватает, чтобы проехать круг полностью, то нельзя, иначе можно.