главная новое лучшее написать

simulation


3

Задача 6-го дня Advent of Code — Guard Gallivant.

📘 Часть I. Описание задачи

Нам требуется смоделировать движение охранника по лаборатории, представленной в виде сетки.

Задача — определить количество уникальных клеток, которые охранник посетит, прежде чем покинет карту.​

💡 Идея

Необходимо симулировать движение охранника, учитывая его текущую позицию и направление. Для отслеживания посещённых клеток используется двумерный массив, где каждая клетка хранит информацию о направлениях, с которых она была посещена. Если охранник возвращается в ту же клетку с тем же направлением, это означает начало цикла.

📘 Часть II. Описание задачи

Во второй части задачи требуется определить количество позиций, где добавление одного нового препятствия приведёт к тому, что охранник зациклится и никогда не покинет карту. Очевидно, что нельзя размещать препятствие в начальной позиции охранника.​

💡 Идея

Читать дальше →

ответить
3

Ссылка на задачу – 3066. Minimum Operations to Exceed Threshold Value II.

📝 Описание задачи

Дан массив nums и число k. Мы можем выполнять следующую операцию, пока в массиве есть хотя бы два элемента:

Необходимо найти количество операций, чтобы все числа в массиве стали ≥ k.

💡 Идея

Мы объединяем два наименьших числа, поэтому важно быстро находить и извлекать их.
Для этого можно использовать очередь с приоритетами (BinaryHeap), но в нашем случае можно действовать эффективнее.

🔹 Заведём две очереди (VecDeque):

Благодаря двум упорядоченным очередям, минимальные элементы можно извлекать за O(1), а вся процедура будет работать эффективнее, чем с BinaryHeap.

Читать дальше →

ответить