Задачки

[Kolobok]

Неувязочка. Только для заполнения первого хранилища нужно 5000 галлонов для езды.

[m_ax]

Неувязочка. Только для заполнения первого хранилища нужно 5000 галлонов для езды.

Почему это 5000 галонов?
Первое хранилище нах. на растоянии 500/3 м. Заправляем полный бак. 1/3 бака тратится на то чтоб до него доехать, 1/3 бака сливаем в хранилище и на оставшейся 1/3 бака едем обратно.
Нам нужно заполнить первое хранилище 5 баками = 5*500 = 2500 галлонов.
Всего для этого нужно 15 баков горючки = 15*500 = 7500 галлонов.
После чего вы находитесь в начале пустыни с пустым баком.
Заливаете ещё один бак чтоб далее доехать до первого хранилища.
Так что всего получается нужно 16 баков горючего т.е. 16*500 = 8000 галлонов.

[Kolobok]

да, моя ошибка.

[_OLEGator_]

А разве не 14 баков необходимо, чтобы заполнить первое хранилище на 2500 галлонов?

от каждой поездки мы заправляем хранилище на 500/3 галлонов
получается, на 13 поездок у нас первое хранилище заполнено на 2000 галлонов + 500/3 галлонов, и мы находимся вначале пустыни с пустым баком.
Заправляемся 14 раз и приезжаем в первое хранилище, где в совокупности с 2/3 бака у нас получается 2500 галлонов

Далее все перевозится во второе хранилище, где в совокупности опять же с этими 2/3 бака получаем 1000 галлонов.
В третьем 500 галлонов и доезжаем до конца пустыни.

У меня получилось 14*500 = 7000 галлонов. Поправьте, если не прав.

[m_ax]

А разве не 14 баков необходимо, чтобы заполнить первое хранилище на 2500 галлонов?

от каждой поездки мы заправляем хранилище на 500/3 галлонов
получается, на 13 поездок у нас первое хранилище заполнено на 2000 галлонов + 500/3 галлонов, и мы находимся вначале пустыни с пустым баком.
Заправляемся 14 раз и приезжаем в первое хранилище, где в совокупности с 2/3 бака у нас получается 2500 галлонов

Далее все перевозится во второе хранилище, где в совокупности опять же с этими 2/3 бака получаем 1000 галлонов.
В третьем 500 галлонов и доезжаем до конца пустыни.

У меня получилось 14*500 = 7000 галлонов. Поправьте, если не прав.

Фишка в том, что находясь в первом хранилище с 5-ю баками горючки (2500 галлонов) вы не сможете заполнить второе хранилище двумя баками (1000 галлонов).

Я имел в виду, что в первом хранилище должно быть 5 баков и вы находясь при этом в начале пустыни, заправляете полный бак, едете к первому хранилищу.
В итоге, находясь у первого хранилища в машине 2/3 бака + 5 баков в хранилище.
Этого достаточно, чтоб наполнить второе хранилище 2 баками и находится при этом на втором хранилище. 

[Igors]

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

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

- чем дальше мы прошли - тем меньше новые шаги (ведь таскать сюда топливо дороже)

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

- проехали 200, дозаправились из первой
- проехали еще 150, дозаправились из второй,
- проехали еще 100, дозаправились из третьей,
- проехали еще 50, дозаправились из 4-й
- проезжаем оставшиеся 500

Поэтому точек 4 (на расстояниях от начала 200, 350. 450, 500)
Перед последним выездом топлива в них должно быть (200, 150, 100, 50) 

Ну а как натаскать и сколько всего литров надо - это, как говорится, "детали реализации" 

[_OLEGator_]

Находясь у первого хранилища с 5-ю баками горючего (2500 галлонов) мы спокойной можем заполнить второе хранилище 1000 галлонами:
после 4 ходок от 1го до 2го хранилища имеем 500 + 500/3 галлонов топлива во 2м хранилище и мы находимся с пустым баком у первого, в котором 500 галлонов топлива.
Заправляем бак, доезжаем до второго хранилища и остается 2/3 бака + топливо во втором хранилище, в совокупности имеем 1000 галлонов топлива.

Дальше заправляем полный бак, доезжаем до 3го хранилища, оставляем 500/3 галлонов, возвращаемся назад, заправляемся оставшимися 500 галлонами, доезжаем до 3го хранилища, где в совокупности с 2/3 бака и 1/3 в хранилище у нас 1 полный бак, дозаправляемся и едем до конца пустыни.

[Igors]

после 4 ходок от 1го до 2го хранилища имеем 500 + 500/3 галлонов топлива во 2м хранилище и мы

Это "слишком конкретно". А будет емкость бака напр всего 100 - как тогда будете складывать в уме/на бумажке? Мне кажется надо идти "с конца", от того расклада что хотим получить

(200, 150, 100, 50) - расклад перед последним выездом, после возвращения в начало. Но мы могли вернуться в начало только из предыдущей (1-й) точки, значит предыдущий расклад (400, 150, 100. 50), и.т.д. до тех пор пока во всех точках не останется по нулям. Расход топлива на каждом шаге добавляем к сумме.

Если точки расставлены - все ясно, но вот сколько и как их ставить - этого я "в общем виде" сформулировать не могу   Пришлось бы подобрать N (число элементов прогрессии) прогнав расчет топлива для каждого

[_OLEGator_]

Igors, эту задачу от частного случая можно свести к общему, просто заниматься сейчас этим не имеет смысла, задача поставлена конкретная - решение в лоб =)

[Igors]

Если точки расставлены - все ясно, но вот сколько и как их ставить - этого я "в общем виде" сформулировать не могу   Пришлось бы подобрать N (число элементов прогрессии) прогнав расчет топлива для каждого

Та чего это не могу? Тут же все просто

d1 = расстояние до первой точки
2 * d1 = топливо затраченное на доставку
500 - 2 * d1 = количество доставленного топлива

Конструируем ф-цию (чем дальше доставили - тем лучше, чем больше доставили - тем лучше, значит)
f = d1 * (500 - 2 * d1)

Это автокорреляционная ф-ция, достигает максимума когда сомножители равны, значит в общем виде оптимальное расстояние до первой точки = 500/3 = 166.6

Расчет для 2-й точки аналогичен, но расходы на доставку растут (ведь сначала надо доставить это топливо до первой точки)
f = d2 * (500 - 2 * d2 - 500 / 3)
тогда d2 = 500 * 2 / 9 = 111.1

и.т.д. ставим точки пока сумма не превысит последнее расстояние

[m_ax]

Находясь у первого хранилища с 5-ю баками горючего (2500 галлонов) мы спокойной можем заполнить второе хранилище 1000 галлонами:
после 4 ходок от 1го до 2го хранилища имеем 500 + 500/3 галлонов топлива во 2м хранилище и мы находимся с пустым баком у первого, в котором 500 галлонов топлива.
Заправляем бак, доезжаем до второго хранилища и остается 2/3 бака + топливо во втором хранилище, в совокупности имеем 1000 галлонов топлива.

Дальше заправляем полный бак, доезжаем до 3го хранилища, оставляем 500/3 галлонов, возвращаемся назад, заправляемся оставшимися 500 галлонами, доезжаем до 3го хранилища, где в совокупности с 2/3 бака и 1/3 в хранилище у нас 1 полный бак, дозаправляемся и едем до конца пустыни.

Да, Вы правы: 5 баков хватит)
Тогда всего получается 7000 галонов нужно.

Igors А у Вас скока всего топлива получается нужно?

[Lagovas]

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

[Igors]

Igors А у Вас скока всего топлива получается нужно?

Давайте считать (точки на расстоянии 200, 350, 100, 50)

- для заправки точек 3 и 4 нужна одна ходка, топлива в них 150 + (300 доставка) = 450
значит точка 2 должна иметь 450 + (150 должно остаться в ней самой) = 600

- для заправки точки 2 (на расстоянии 150) надо 3 ходки = 1500, из них доставка = 900
значит точка 1 должна иметь 1500 + (200 должно остаться в ней самой) = 1700

- для заправки точки 1 (на расстоянии 200) надо 17 ходок, доставка = 17 * 300 = 5100

Складываем все расходы на доставку: 300 + 900 + 5100 = 6300
Итого доставка + финальный заезд: 6300 + 1000 = 7300

[Lagovas]

нет, можно еще меньше.

[kambala]

линейное программирование надо применять?