"В пробке на Московском мосту есть "N" автомобилей, где N-некоторое целое число. Каждый автомобиль можно мыть белым, желтым или фиолетовым шампунем. За каждый автомобиль Вы будете зарабатывать различное значение денег.
Выясните, как мыть каждый автомобиль, чтобы никакие две соседние машины не имели одинакового цвета шампуня, а общие деньги на мытье всех автомобилей были как можно выше." (с)
Другие языки программирования и технологии
Подскажите пожалуйста решение такой задачи.
Ну начнем с того, что за Московский мост.
Московский мост находится в Киеве, в этом году был переименован в Северный, имеет по 3+1 полосы в каждую сторону и имеет длину 816 метров.
Длина обычного легкового автомобиля около 4 метров.
Значит
N ~ (816 / 4) * 4
N ~ 816
Итак, выходит, что чтобы образовалась пробка на Московском мосту, нужно примерно 816 автомобилей (в реальности меньше). Поэтому то, что N - переменная, очень напрягает.
Ну а теперь к задаче.
Если допустить, что длина каждого автомобиля одинакова, то они могут быть расположены в своих полосах в ряд или со смещением.
В первом случае, автомобили необходимо вымыть двумя самыми дорогими "шампунями" в шахматном порядке. Таким образом выйдет, что суммарная выручка за помывку всех автомобилей будет равна P1*ceil(N/2) + P2*floor(N/2), где P1 - стоимость самого дорогого шампуня, P2 - стоимость среднего по стоимости шампуня, N - количество автомобилей, ceil(x) - округление к большему, floor(x) - округление к меньшему
В случае, если автомобили не равной длины или расположены не в ряд, то, по теореме четырех красок, может и не оказаться способа выполнить условие.
Московский мост находится в Киеве, в этом году был переименован в Северный, имеет по 3+1 полосы в каждую сторону и имеет длину 816 метров.
Длина обычного легкового автомобиля около 4 метров.
Значит
N ~ (816 / 4) * 4
N ~ 816
Итак, выходит, что чтобы образовалась пробка на Московском мосту, нужно примерно 816 автомобилей (в реальности меньше). Поэтому то, что N - переменная, очень напрягает.
Ну а теперь к задаче.
Если допустить, что длина каждого автомобиля одинакова, то они могут быть расположены в своих полосах в ряд или со смещением.
В первом случае, автомобили необходимо вымыть двумя самыми дорогими "шампунями" в шахматном порядке. Таким образом выйдет, что суммарная выручка за помывку всех автомобилей будет равна P1*ceil(N/2) + P2*floor(N/2), где P1 - стоимость самого дорогого шампуня, P2 - стоимость среднего по стоимости шампуня, N - количество автомобилей, ceil(x) - округление к большему, floor(x) - округление к меньшему
В случае, если автомобили не равной длины или расположены не в ряд, то, по теореме четырех красок, может и не оказаться способа выполнить условие.
дорога многополосная?
вымыть их поочередно парой самых дорогих шампуней и всего делов.
вымыть их поочередно парой самых дорогих шампуней и всего делов.
А мы знаем зараее цену за каждый шампунь?
P.S. Ну шампунем автомобиль мыть, это конечно сильно
P.S. Ну шампунем автомобиль мыть, это конечно сильно
Mihail Shlosman
Я, полагаю, это дословный перевод с английского "car shampoo"
Ибо, например "значение денег", скорее всего, тоже перевод с "amount of money"
Ибо, например "значение денег", скорее всего, тоже перевод с "amount of money"
Похожие вопросы
- подскажите алгоритм решения 386 задачи на acmp.ru http://www.acmp.ru/index.asp?main=task&id_task=386
- Подскажите пожалуйста как такую задачу на СИ решать?
- Объясните решение этой задачи Пожалуйста
- Запутываюсь при решении логических задач, написании программ
- Мне задали сделать задачу по Turbo Pascal, но я забыл что нужно писать в var и READ. подскажите пожалуйста.
- Составьте программу решения старинной задачи: сколько можно купить быков (бык стоит 10рубей) , коров (по 5 рублей) и тел
- Помогите найти ошибку в решении олимпиадной задаче...
- Зачем нужен решение математические задачи в программировании
- Пожалуйста, помогите составить программы для решения следующих задач.
- Помогите пожалуйста составить решение с задачей по программированию(на любом языке программирования)
к этому исчерпывающему ответу можно лишь добавить, что если автомобили имеют одинаковую длину, то в худшем случае образуют узлы треугольного паркета, и их можно вымыть как раз тремя шампунями.