23.08 Прочие прототипы
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок находится на первой ступеньке очень длинной лестницы. У исполнителя есть 3 команды:
1. Подняться на одну ступеньку и потратить одну единицу энергии.
2. Перешагнуть через одну ступеньку (подняться на две) и потратить 3 единицы энергии
3. Перешагнуть через две ступеньки (подняться на 3 ступеньки) и потратить 6 единиц энергии
Программа для исполнителя — это последовательность команд.
У исполнителя в запасе 60 единиц энергии, длина лестницы 25 ступенек. За какое минимальное количество команд исполнитель сможет добраться до последней ступеньки и сохранить максимальный для такого количества команд запас энергии. Если запас энергии исполнителя кончается, он отчаивается и не идет дальше, кроме случая, если он уже на 25 ступеньке. В ответе укажите количество команд и максимальный сохраненный запас энергии.
Решение 1 (Рекурсия)
from functools import lru_cache @lru_cache(None) def f(st, fn, en, comand): global count, ener if st == fn and en >= 0: if comand < count: count = comand ener = en #если количество шагов совпало, # то мы берем максимум энергии elif comand == count and en > ener: ener = en return # вылет из программы if en < 0: return f(st + 1, fn, en - 1, comand + 1) f(st + 2, fn, en - 3, comand + 1) f(st + 3, fn, en - 6, comand + 1) count = 10000000 ener = -1 f(1, 25, 60, 0) print(count, ener)
Решение 2 (Динамика)
ans = [] ans.append((1, 60, 0)) # (текущая ступенька, текущее кол-во энергии, кол-во сделанных ходов) otv, mn_com = -100000000, 100000000 for operations in range(1000): can_get = [] for i in ans: step, energy, go = i if (step > 25) or (energy < 0): continue if (step == 25) and (energy >= 0): if mn_com == go: # берем минимум команд и максимум энергии mn_com = go otv = max(otv, energy) continue elif mn_com > go: mn_com = go otv = energy continue # все возможные ходы can_get.append((step + 1, energy - 1, go + 1)) can_get.append((step + 2, energy - 3, go + 1)) can_get.append((step + 3, energy - 6, go + 1)) # если больше ходов нет, выходим из цикла if len(can_get) == 0: break ans = can_get.copy() print(mn_com, otv)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
