SOS

← →
LeViSSSS © (2002-11-06 13:57) [0]

Есть такая задача:
Однажды ночью гроуппа из N путнков подошлша к мостику через глубокую пропасть. Мостик оказался настолько ветхим, что мог выдержать не более 2 путников одновременно. Чтобы преодолеть мостик и не сорваться в пропасть, путники должны освещать себе дорогу. У путников оказался только один фонарь, а веруть фонарь обратно на другую сторону пропасти, можно только перейдя через мостик. Путники обладают разной ловкостью и переходят через мостик за различное время. Время перехода для группы из двух путников равно времени для перехода самого медленного из двух путников.
напишите программу, которая на основе информации о количестве путников N введённой в txt файле Input.txt и времени перехода для одного путника введённой там же, только на строчку ниже. В выходном файле output.txt должна содержаться строка с одним целым числом - минимальным временем перехода через мостик для группы.

Заранее спасибо....ответ на vitalik1@rambler.ru

← →
Ru © (2002-11-06 15:26) [1]

Время перехода всей группы: N*2-1
либо необходимо уточнить задачу и вводить время перехода каждого.
Если я правильно понял условие.

← →
Igorek © (2002-11-06 15:43) [2]

Пусть Tmin - время перехода самого быстрого путника. Ti - время любого другого i = [0 .. N-1].
Алгоритм такой: самый быстрый переводит каждого другого путника и возвращается обратно с фонарем.
Общее время (минимальное одновременно):
(N-2)*Tmin + T0 + T1 + T2 +...+ T(N-1)

← →
AL2002 © (2002-11-06 15:47) [3]

> LeViSSSS © (06.11.02 13:57)

Это, наверное, группа шкодеров под предводительством Сатира мостик переходила.

← →
Mist (2002-11-06 16:10) [4]

Мне эту же зачу кинули мылом в таком виде
(говорят, что она точно решается)

Сидят четверо ночью на берегу реки, перед ними опасный мост, им позарез надо перейти мост за 14 минут. При этом у них только один фонарь, а мост выдерживает одновременно двоих человек, не больше. Без фонаря пройти нельзя.
Первый проходит мост за 1 мин, второй - за 2 мин, третий - за пять, четвертый - за 7. Как им преодолеть мост за 14 мин?

← →
Ru © (2002-11-06 17:04) [5]

Я ж говорил данных маловато!

>Mist (06.11.02 16:10)

при такой постановке за 16 минут.

Тогда решение следующее:
1 находим минимальное время
2 находим сумму всех значений времени + N-1 минимальных значений

← →
Ru © (2002-11-06 17:16) [6]

ой N-2

← →
LongIsland © (2002-11-06 17:19) [7]

> AL2002 © (06.11.02 15:47)
> Это, наверное, группа шкодеров под предводительством Сатира
> мостик переходила.

Я попрошу нашу птичку не обижать:-))))

← →
LongIsland © (2002-11-06 17:25) [8]

> Mist (06.11.02 16:10)

Я могу их переправить за 11 мин.:-)

← →
TTCustomDelphiMaster © (2002-11-06 17:32) [9]

> Ru © (06.11.02 17:04)
> Я ж говорил данных маловато!
>
> >Mist (06.11.02 16:10)
>
> при такой постановке за 16 минут.

И все таки за 14

2+1+7+2+2=14

← →
Ru © (2002-11-06 17:32) [10]

>LongIsland © (06.11.02 17:25)

?

← →
Ru © (2002-11-06 17:40) [11]

>TTCustomDelphiMaster © (06.11.02 17:32)

а где 5-ти минутный?

← →
LongIsland © (2002-11-06 17:46) [12]

> Ru © (06.11.02 17:32)

Под мышкой, тяжело уставая:-))) В расчеты вкралась предательская ошибка:-)))))

В таком случае есть решение (N+1)*Tmin
самый шустрый всех на гиргошах перетащит Ж:)

буду нумеровать людей по времени прохода.
1) 1&2 -> 2
2) 1 <- 1
3) 1&5 -> 5
4) 1 <- 1
5) 1&7 -> 7

Итого: 2+1+5+1+7=16 Не меньше.
Все съедает возврат самого быстрого :(((
О! Идея! А может поставить самого быстрого на мост? Пускай дойдет до середины с любым (например, с 7), а от середины до конца - с последним (напр, 2)? Остальные-же будут проходить по одному...

SOS Найти похожие ветки