Взято с asmoth.me
Продолжаем разбирать задачи челленджа
Это уже вторая часть и она немного запоздала, т.к. я отвлекся на статью о конкурсе от Пикабу. В этой части будет разбор трех задач третьего уровня, а в следующей части все оставшиеся задачи. Для тех кто пропустил:
Google Foo.Bar Challenge 2019. Часть 1
Приступим в разбору!
Level 3–1. Find the Access Codes
Для того, чтобы уничтожить устройство LAMBCHOP конца света Командующей Лямбды, вам понадобится доступ к нему. Но единственная дверь, ведущая в камеру LAMBCHOP, защищена уникальной шлюзовой системой, количество кодов которой меняется ежедневно. Командующая Лямбда каждый день получает отчет, содержащий коды доступа к замкам, но только она знает, как выяснить, в каком из нескольких списков содержатся коды доступа. Вам необходимо найти способ определить, в каком списке находятся коды доступа, когда вы будете готовы войти в систему.
К счастью, теперь, когда вы являетесь личным помощником Командующей Лямбды, она призналась вам, что она сделала все коды доступа “счастливыми тройняшками”, чтобы помочь ей лучше найти их в списках. “Счастливые тройняшки” — это сочетание (x, y, z), где x делит y и y делит z, например (1, 2, 4). С помощью этой информации вы сможете определить, какой список содержит количество кодов доступа, соответствующее количеству замков на двери, когда будете готовы войти (например, если есть 5 паролей, вам понадобится список с 5 “счастливыми тройными” кодами доступа).
Напишите функцию solution(l), которое принимает список положительных целых чисел l и подсчитывает число “счастливых тройняшек” (li, lj, lk), где индексы списка соответствуют требованию i < j < k. Длина l от 2 до 2000 включительно. Элементы l находятся в диапазоне от 1 до 99999999 включительно. Ответ помещается в знаковое 32-битное целое число. Некоторые из списков специально сгенерированы без кодов доступа, чтобы запутать шпионов, поэтому если тройняшек не найдено, верните 0.
Например, [1, 2, 3, 4, 5, 6] содержит тройняшки: [1, 2, 4], [1, 2, 6], [1, 3, 6], в результате чего ответ получается 3.
Первый вариант который я написал это был рекурсивный поиск по остатку массива на предмет кратных чисел и составление “тройняшек”, алгоритм работал, но на больших данных это было медленно.
Второй вариант уже намного лучше. При прохождении по массиву мы берем число как y и проходимся в обе стороны сравнивая потенциальные x и z по условию, попутно считая их. Получившееся количество x умножаем на количество z и мы получим количество комбинаций при данном y. Таким образом пройдясь по массиву мы посчитаем количество всех комбинаций без надобности создания массивов и без рекурсии.
Level 3–2. Fuel Injection Perfection
Командующая Лямбда попросила вас помочь усовершенствовать автоматическую систему впрыска квантового антивещества для ее устройства судного дня LAMBCHOP. Это отличный шанс для вас ближе познакомиться с LAMBCHOP — и, возможно, получится устроить саботаж, пока вы рядом с ним, — так что вы с радостью взялись за эту работу.
Квантовое антивещество поставляется в виде небольших упаковок, что удобно, так как в каждую движущуюся часть LAMBCHOP необходимо подавать по одной упаковке топлива за раз. Тем не менее, миньоны сбрасывают упаковки кучей в топливный бак. Необходимо найти наиболее эффективный способ сортировки и перемещения упаковок до одной упаковки за раз.
Механизмы контроля топлива функционируют в трех направлениях:
1) Добавить одну упаковку топлива
2) Удалить одну упаковку
3) Разделить кучу упаковок топлива на 2 (из-за разрушительной энергии, высвобождающейся при разрезании гранул квантовой антиматерии пополам, органы безопасности позволят это сделать только при четном количестве упаковок).
Напишите функцию под названием solution(n), которая принимает строкой целое положительное число и возвращает минимальное количество операций, необходимое для преобразования количества упаковок до одной. Прибор может отображать только число до 309 знаков в длину, поэтому количество упаковок не будет превышать, чем вы можете выразить в таком количестве цифр.
Примеры:
solution(4) возвращает 2: 4 -> 2 -> 1
solution(15) возвращает 5: 15 -> 16 -> 8 -> 4 -> 2 -> 1
Будем считать количество операций в бесконечном цикле пока не останется одна упаковка. Если количество упаковок n делится на 2, то мы делим пополам. В противном случае, если n равно 3 или остаток от деления на 4 равно 1, то мы отнимаем одну упаковку, если нет то добавляем одну. В конце итерации цикла добавляем к количеству операций count единицу.
Почему второе условие проверяет именно на 3 и остаток от деления на 4 равном 1? Все просто. Разберем пример:
Даны числа от 1 до 14.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
Если из них выделить числа кратные 4 и посмотреть на числа между них то можно увидеть, что например числу 5 выгоднее преобразоваться в 4 чем в 6, как раз остаток от деления на 4 равен 1. Число 6 делится на 2 и дальше вычисляется. Семерке без разницы, оба пути до конечного результата одинаковые по длине. Всем числам перед числом кратному 4 выгодно прибавлять единицу, кроме 3 на этом примере все наоборот. Можете сами все расписать на бумаге и будет понятно.
Level 3–3. Prepare the Bunnies’ Escape
Вы ужасно близки к уничтожению устройства конца света LAMBCHOP и освобождения заключенных кроликов Командующей Лямбда, но как только они освободятся из тюремных блоков, кролики будут нуждаться в побеге с космической станции Лямбда через спасательные капсулы как можно скорее. К сожалению, залы космической станции — это лабиринт коридоров и тупиков, который станет смертельной ловушкой для спасающихся кроликов. К счастью, Командующая Лямбда поручила вам проект реконструкции, который даст вам возможность немного облегчить жизнь кроликам. К сожалению (опять же), вы не можете просто снять все препятствия между кроликами и аварийными капсулами — в крайнем случае, вы можете снять по одной стене на каждый путь до аварийной капсулы, чтобы сохранить целостность структуры станции и избежать возникновения подозрений у Командующей Лямбда.
У вас есть карты частей космической станции, каждая из которых начинается с выхода из тюрьмы и заканчивается у двери спасательной капсулы. Карта представлена в виде матрицы нулей и единиц, где нули — это проходное пространство, а единицы — непроходимые стены. Дверь из тюрьмы сверху слева (0,0), а дверь в спасательную капсулу внизу справа (w-1, h-1).
Напишите функцию solution(map), которое генерирует кратчайший путь от тюремной двери до спасательной капсулы, где вам разрешено убрать одну стену в рамках ваших планов реконструкции. Длина пути — это общее количество узлов, через которые вы проходите, с учетом как входных, так и выходных узлов. Начальное и конечное положения всегда являются допустимыми (нулями). Карта всегда будет разрешима, хотя вам может понадобиться удалить стену, а может и не понадобиться. Высота и ширина карты может быть от 2 до 20. Перемещения могут осуществляться только в кардинальных направлениях; диагональные перемещения не допускаются.
Здесь берем матрицу и клонируем, удаляем одну стенку и пробуем решить и так пока не переберем все варианты, при этом запоминая длину самого короткого пути.
Заполняем в цикле матрицу пока не достигнем конца или не сможем пройти дальше. Если достигли конца то запоминаем число в ячейке выхода из лабиринта, в ней находится цифра отображающая количество шагов.
Вариант не самый идеальный, BFS (Breadth-first search, поиск в ширину) будет работать намного быстрее.
Ну чтож осталось написать разбор последних трех задач этого челленджа. Подписывайтесь, чтобы не пропустить мою следующую писанину. Есть пара инвайт кодов, есть желающие попробовать?
