23.09 Нестандартные задачи
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок взял пример с 
задания, купил 
саженца и переехал в волшебную страну. Деревьев в этой
стране нет, поэтому нарубить дров исполнитель не может. Почва в волшебной стране, разумеется, волшебная, если
посадить 
саженцев, то они вырастут в деревья за 
дней. При этом, деревья, посаженные в разные дни,
растут независимо друг от друга, т.е. если в первый день посадили 
саженца, а во второй еще один, то к
третьему дню можно будет спилить 
дерева. Каждое дерево дает 
единиц дров и 
новых саженца.
Исполнитель хочет узнать за какое минимальное количество дней он сможет собрать минимум 
единиц
дров.
Решение 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)
