Задача 6-го дня Advent of Code — Guard Gallivant.
📘 Часть I. Описание задачи
Нам требуется смоделировать движение охранника по лаборатории, представленной в виде сетки.
- Охранник начинает в определённой клетке, смотрит в одном из четырёх направлений и следует следующим правилам:
- Если перед ним препятствие (
#
), он поворачивает направо на 90°
.
- Иначе делает шаг вперёд.
Задача — определить количество уникальных клеток, которые охранник посетит, прежде чем покинет карту.
💡 Идея
Необходимо симулировать движение охранника, учитывая его текущую позицию и направление. Для отслеживания посещённых клеток используется двумерный массив, где каждая клетка хранит информацию о направлениях, с которых она была посещена. Если охранник возвращается в ту же клетку с тем же направлением, это означает начало цикла.
📘 Часть II. Описание задачи
Во второй части задачи требуется определить количество позиций, где добавление одного нового препятствия приведёт к тому, что охранник зациклится и никогда не покинет карту. Очевидно, что нельзя размещать препятствие в начальной позиции охранника.
💡 Идея
Читать дальше →
Ссылка на задачу – 3066. Minimum Operations to Exceed Threshold Value II.
📝 Описание задачи
Дан массив nums
и число k
. Мы можем выполнять следующую операцию, пока в массиве есть хотя бы два элемента:
- Взять два наименьших числа
x
и y
.
- Удалить их из массива.
- Добавить новое число
2·min(x,y) + max(x,y)
.
Необходимо найти количество операций, чтобы все числа в массиве стали ≥ k
.
💡 Идея
Мы объединяем два наименьших числа, поэтому важно быстро находить и извлекать их.
Для этого можно использовать очередь с приоритетами (BinaryHeap
), но в нашем случае можно действовать эффективнее.
🔹 Заведём две очереди (VecDeque
):
orig_values
— содержит исходные числа < k
, отсортированные по возрастанию.
new_values
— хранит новые числа, появляющиеся в процессе операций, в гарантированно возрастающем порядке.
Благодаря двум упорядоченным очередям, минимальные элементы можно извлекать за O(1)
, а вся процедура будет работать эффективнее, чем с BinaryHeap
.
Читать дальше →