Есть кольцевая дорога длиной 100 км, на которой произвольным образом разбросано конечное число бочек с горючим. Суммарное количество горючего в бочках 100 л, но распределение горючего по бочкам произвольно. Есть автомобиль с расходом топлива 1 л/км и пустым баком вместимостью >100 л. Можно ли объехать всю дорогу в каком либо направлении?

Перед поездкой ваш автомобиль (с пустым баком) по вашему желанию доставят к любой из бочек

в общем случае, нет

(0) возможно, но только в одну сторону

(1)(2) мнения разделились
да, сторону объезда вы вольны выбирать сами

(2) + если есть возможность смотреть карту, где какая бочка + количество в ней горючего

(2) +1. Бак достаточно иметь 100-литровый, всё равно больше 100 л топлива оказаться там не может.

если только ходить до бочки с канистрой, если не доехал.
Иначе +1 к (1).

Низя, пустой бак как до бочки то доехать...

блин лохонулся)

(2)+1

(2) ответ зависит от начального выбора водителя. если он будет исходить из того, что ему обязательно НАДО проехать полный круг, и он выберет оптимальную начальную точку при известной дислокации запасов горючего (местоположение бочек и объём находящегося в них горючего), то да, а если он просто говорит - доставьте меня вот к этой (произвольной) бочке, то может и не хватить топлива

(10)  -> (3)

но, поскольку условие оптимальности выбора начальной точки водителем в (0) не заявлено, то (1)

Объехать можно, доказательство наглядное. Каждую бочку представим как дугу (часть окружности), длиной в столько км, на сколько хватит в ней горючего. Сама бочка изначально на любом конце дуги. Получается, если автомобиль стартует с конца дуги, то может проехать ее всю. Если дуги пересекаются, можно их раздвинуть, чтобы они стали только соприкасаться. Ну а в сумме дуги полностью покроют всю дорогу.

(13) прикинь, портнули тебя к бочке №37, а там внутри пусто

(14) Я сам выбираю откуда стартовать.

(13)>>Каждую бочку представим как дугу (часть окружности), длиной в столько км, на сколько хватит в ней горючего
Нет такого в условии. А если поставить дальше?

Если в первой бочке бензина меньше, чем надо доехать до любой следующей, то полюбому толкать придется. Также как если расстояние до третьей минус больше чем было топлива в первых двух минус расстояние между первой и второй. И т.д.

(15) ну хорошо, вот тебе 100 бочек. выбирая. какую выбираешь?

Допустим что 50 литров расположено в начале и 50 литров в конце, тогда какую точку старта ни выбирай, все равно не доедешь. (10), то есть от оптимальности выбора начальной точки зависит не все

(15)а бочки-то стоЯт не так, как тебе хочется....

(18) оптимальность выбора начальной точки и сразу же - выбор направления движения

(16)(17) Перебором найду бочку, от которой дуга протянется по всей окружности. Минимум одна такая будет.

(20), если бочки будут расположены как я написал, то никак не доедешь.

(18) это же круг

(22) "Есть >>> кольцевая <<< дорога"

перед выбором места старта и направления объем каждой бочки известен водителю, водитель не идиот, он реально хочет проехать круг

(24), как чувствовал, что чего-то упустил=)

(13) ты не учел, что раздвигать можно только в одну сторону (по движению)

(27) А это важно? Главное, что после всех "раздвиганий" дуги полностью покроют всю дорогу.

Доставьте меня с автомобилем к бочке, в которой больше всего горючего - и я проеду полный круг :)

(28) уговорил

(29) врешь, я поставлю тебя с бочкой 40 литров, две бочки по 30 литров ждут тебя недалеко от противоположной точки))

(25) тогда в чём соль?

(32) и сахар ))

(32) соль, например, в том, что стратегия (29) не рабочая

(33) а, ты хочешь сказать, что в одной из бочек с топливом подмешан сахар? :)

(34) а при чём здесь стратегия? с учётом (25) никакой интриги не остаётся

(36) не нравится, решай это http://forum.infostart.ru/forum14/topic64936/message706707/#message706707

(31) Хех. Тогда давай заранее бочки раставляй, называй где сколько горючего. А я тебе скажу точку откуда я начну, чтобы проехать полный круг.

Не важно как бочки раставленны и сколько в них горючего - знаю эту информацию - всегда можно проехать полный круг.

(32)+1
?

Тут другой вопрос назревает, как выбрать 1-ю бочку и направление движения?

Может проще с другой стороны: как расставить N бочек, чтобы не было ни одного маршрута из 2*N (каждый состоит из N-1 отрезков), где сумма с накоплением для каждого отрезка >= 0.
имхо (2)+1

Направление, кстати, неважно. Всегда можно объехать дорогу в любом направлении.

(43) но оно зависит от стартовой позиции

(44) Наоборот, стартовая позиция зависит от выбранного направления.

Как можно НЕ доехать я НЕ придумал.
Соответственно вывод что:
МОЖНО.

(45) +1 согласен. Выбор направления определяет начальную точку (или подмножество точек). Если наобороть поступить (начальная точка - первично, а направление - вторично), то можно и не доехать :)

(45)(47) стартовая позиция + направление = маршрут. Всегда ли число возможных маршрутов четное?
Фиксация направления, это просто сокращение количества проверяемых маршрутов на 2.

203.55
209.84

Приведем сначала задачу к дискретному случаю, а именно: разобьем кольцо на N маленьких РАВНЫХ отрезочков, где N очень большое.
Считаем при этом, что бочка может стоять только на конце отрезка.
Тогда последовательности А(1)...А(N) соответствуют точки-концы отрезков и A(k)=0 означает, что в этой точке нет бочки, либо А(к)=объем бочки в точке k. По условию Сумма(А(1)...А(N))=100 Разомкнем кольцо следующим образом, добавим в последовательность члены A(N+1)=A1, А(N+2)=A(2)....A(2*N)=AN
Очевидно, что Сумма(А(1)...А(2N))=200

Тогда условие недоезжания машинки при определенной расстановке бочек сводится к следующему:
Существует такая последовательность А(1)...А(2*N), где все члены положительны и Сумма(А1...АN)=100, что для любого k от 1 до N (точка выбираемая водителем для старта) Существует такое m (длина на которой заглохнет), что
Сумма(А(к),А(к+1),....А(к+m))<[100/N]*m что означает русским языком что какую бы точку не выбрал водитель, чтобы стартовать, всегда существует такой отрезок, что сумма всех бочек на этом отрезке меньше чем бензин необходимый для проезжания этого отрезка.

Допустим такая расстановка бочек существует, возьмем к=1, тогда существует m1, что
Сумма(А(1)...А(m1))<[100/N]*m1
Возьмем теперь k=m1+1, тогда опять существует такое m2, что
Сумма(А(m1+1)...А(m1+m2))<[100/N]*m2

Продолжаем эти суммы пока не дойдем до точки A(2N), теперь сложим у всех неравенств левые и правые части, получим
Сумма(А(1)....А(m1),A(m1+1)....A(m1+m2).....A(2N))<[100/N](m1+m2+....)
В левой части у нас просто сумма всей последовательности, которая равна 200
в правой части имеем m1+m2+....=2N=200
Отсюда имеем 200<200 что неправильно. А значит такая расстановка невозможна.

Значит при любой расстановке бочек всегда можно подобрать такой старт что Сумма бочек по пути будет всегда больше пройденного расстояния.

Можно в любую сторону.

(49) Забыл сказать, уменьшением отрезка и увеличением N до бесконечности задача сводится к недискретному случаю.

Следствие: Т.к. не существует последовательности бочек которую нельзя проехать то переставляя бочки наоборот в обратном порядке, мы такую последовательность не получим. А значит МКАД можно проехать в любую сторону, как по часовой так и против

(51) А вот тут мы вас поправим.

1-й км, бочка 1 л.

3-й км, бочка 99 л.

(52) Проезжается от бочки 99л в любую сторону

Выбирая первую бочку.. Заведомо все проедешь. Если не ошибешься в выборе бочки. :)

Можно, в любую сторону

(53) Я возражал утверждению "можно проехать в любую сторону". Подразумевая "с той же исходной бочки", что было моим домыслом.

Короче - проще заработать на полный бак, чем сидеть над этой задачей.

(56) Своих домыслов не надо

+(55)
Это настолько очевидно, что даже влом доказывать.
Доказательство "от обратного" потребует совсем мало времени

Можно в любую сторону.