Ручная работа
Задачу добавил: alef
Успешно сдано решений: 28
Утром до работы смогли добраться только N сотрудников фирмы "Лето красное". Однако подойти к входной двери не представлялось возможным. У фирмы два подсобных помещения, в одном из которых находится K снеговых лопат, а в другом - M снеговых лопат, но подходы к ним также завалены снегом (см. рис.)
Сотрудники ООО "Белый шум" одолжили им L лопат. Один сотрудник фирмы "Лето красное" (одной лопатой) за единицу времени может расчистить S единиц длины дороги. От места, где находятся сейчас сотрудники, до одного из подсобных помещений расстояние DK, до другого - DM, длина дороги, которую надо расчистить, составляет DL.
И теперь сотрудники фирмы "Лето красное" обдумывают, как им следует действовать, чтобы быстрее расчистить дорогу к входной двери.
Они могут расчищать уже имеющимися лопатами дорогу к входной двери, могут расчистить сначала дорогу к какому-то из подсобных помещений, взять дополнительные лопаты, и затем либо чистить дорогу к другому подсобному помещению, чтобы взять лопаты еще и оттуда, либо чистить сразу основную дорогу. Наконец, они могут разделиться – часть людей с лопатами будет расчищать дорогу к подсобному помещению (или помещениям), одновременно с ними другая часть - основную дорогу.
Ваша задача - определить минимальное время, за которое они могут расчистить основную дорогу. Также выясните, сколько единиц длины им придется очистить от снега.
Сотрудники в процессе расчистки не мешают друг другу. Если сотрудник начал чистить дорогу к подсобному помещению, то он не может уйти чистить другую дорогу до тех пор, пока дорога к подсобному помещению не будет расчищена.
Формат входного файла input.txt
Первая строка - целые числа N, K, M, L через пробел (1 <= N <= 20, 0 <= K <= 20, 0 <= M <= 20, 1 <= L <= 5)
Вторая строка - целые числа S, DK, DM, DL через пробел (1 <= S <= 10, 1 <= DK, DM, DL <= 100000)
Формат выходного файла output.txt
Первая строка - целое число P и через пробел вещественное число T с точностью 0.00001 - соответственно суммарное расстояние, которое придется очистить от снега сотрудникам фирмы, и минимально возможное время, в течение которого они расчистят дорогу к главному входу.
Пример входного файла
5 1 6 2
5 25 10 18
Пример выходного файла
28 1.72000