Без кэша: унаследованные скидки
Почему это важно "Это повторяет работу, так что запомни ответы" - одна из сильнейших привычек в программировании, у людей и у ИИ. Иногда работу вообще не нужно повторять.
Категории магазина образуют дерево: Garden стоит под Home, Tools под Garden и так далее. Маркетолог может задать скидку на любую категорию, и она применяется ко всему ниже неё, если только более близкая категория не задаёт свою. Касса ищет действующую скидку сразу для тысяч категорий.
Данные
parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25} # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]Очевидное исправление повторных подъёмов по дереву - кэш. В этой задаче кэши запрещены. Ищите способ, который вообще никогда не повторяет работу.
Напишите effective_discounts(parents, own, queries). parents сопоставляет каждой категории её родителя или None для категории верхнего уровня (их может быть несколько, и dict без определённого порядка). own сопоставляет некоторым категориям их собственную скидку. Для каждой категории в queries верните скидку ближайшей категории на её пути к вершине, начиная с неё самой, у которой она есть в own; 0, если ни у одной нет. Правило: никакого кэша или memo: никаких кэширующих декораторов functools, никаких имён, содержащих "cache" или "memo", и никакого вычисления ответов по мере того, как их спрашивают запросы, с их сохранением (memo под другим именем). Сначала пройдите всё дерево, затем читайте запросы. Бюджет: не больше 500 000 шагов (steps()) для 3 000 категорий, деревьев глубиной до нескольких сотен уровней и 20 000 поисков.
Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке
Это упражнение откроется скоро
Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.
Этот браузер блокирует cookies для learn.floati.life, поэтому завершенные здесь уроки не могут открыться по порядку. Разрешите cookies для этого сайта и перезагрузите страницу.