Тема 23. Линейные программы и ветвление

23.09 Нестандартные задачи

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела линейные программы и ветвление
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#30495

Исполнитель Щелчок взял пример с 26  задания, купил 3  саженца и переехал в волшебную страну. Деревьев в этой стране нет, поэтому нарубить дров исполнитель не может. Почва в волшебной стране, разумеется, волшебная, если посадить n  саженцев, то они вырастут в деревья за n  дней. При этом, деревья, посаженные в разные дни, растут независимо друг от друга, т.е. если в первый день посадили 2  саженца, а во второй еще один, то к третьему дню можно будет спилить 3  дерева. Каждое дерево дает 10  единиц дров и 2  новых саженца. Исполнитель хочет узнать за какое минимальное количество дней он сможет собрать минимум 200  единиц дров.

Показать ответ и решение

Решение 1 (Рекурсия)

def f(day, count_drova, count_sajenec, days, tree):
    global minim
    if day > minim: # если день перешел минимальное количество дней,
        # то мы заканчиваем
        return
    i = 0
    while i < len(days): # массив дней, когда должны вырасти очередные деревья
        if days[i] == day:
            days.pop(i)
            a = tree.pop(i)
            count_drova += 10 * a # растет количество дров
            count_sajenec += 2 * a # растет количество саженцев
            i -= 1 # -1 тут и +1 ниже скомпенсируют удаленный элемент
        i += 1
    if count_drova >= 200 and day < minim:
        minim = day
        return
    for i in range(1, count_sajenec + 1):
        if i * 10 + count_drova > 200: # не нужно рассматривать варианты,
            # которые будут заведомо дольше чем мы хотим
            break
        # посадили i деревьев
        f(day + 1, count_drova, count_sajenec - i, days.copy() + [i + day],
          tree.copy() + [i])
minim = 10000000000
f(1, 0, 3, [], [])
print(minim)

Решение 2 (Динамика)

ans = []
ans.append((1, 0, 3))
# (сколько прошло дней, сколько есть дров, сколько есть саженцев)
otv = 10000000
for operations in range(1000):
    can_get = []
    for i in ans:
        days, wood, seed = i
        if wood >= 200:
            otv = min(otv, days)
            continue
        for j in range(1, seed + 1):  # сажаем j саженцев
            if j == 1:
                can_get.append((days + j, wood + j * 10, seed + j))
            else:
                can_get.append((days + j - 1, wood + j * 10, seed + j))
    if len(can_get) == 0:
        break
    ans = can_get
print(otv)

Ответ: 10
Рулетка
Вы можете получить скидку в рулетке!