Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Гоблины и шаманы.
Сложность: Средняя.
Статус решения: "Решено".
Условие задачи:
Гоблины Мглистых гор очень любят ходить к своим шаманам. Так как гоблинов много, к шаманам часто образуются очень длинные очереди. А поскольку много гоблинов в одном месте быстро образуют шумную толпу, которая мешает шаманам проводить сложные медицинские манипуляции, последние решили установить некоторые правила касательно порядка в очереди.
Обычные гоблины при посещении шаманов должны вставать в конец очереди. Привилегированные же гоблины, знающие особый пароль, встают ровно в её середину, причем при нечётной длине очереди они встают сразу за центром.
Так как гоблины также широко известны своим непочтительным отношением ко всяческим правилам и законам, шаманы попросили вас написать программу, которая бы отслеживала порядок гоблинов в очереди.
Формат ввода (input):
В первой строке входных данный записано число N (1≤N≤1051≤N≤10 в пятой степени)— количество запросов к программе. Следующие N строк содержат описание запросов в формате:
''+ i'' — гоблин с номером i (1≤i≤N1≤i≤N) встает в конец очереди.
''* i'' — привилегированный гоблин с номером i встает в середину очереди.
''-'' — первый гоблин из очереди уходит к шаманам. Гарантируется, что на момент такого запроса очередь не пуста.
Формат вывода (Output):
Для каждого запроса типа ''-'' программа должна вывести номер гоблина, который должен зайти к шаманам.
Решение:
Python
import sys
from collections import deque
def main():
# Используем два deque для эффективного управления очередью
left = deque() # Первая половина очереди
right = deque() # Вторая половина очереди
output = [] # Для хранения результатов запросов типа '-'
# Чтение количества запросов
n = int(sys.stdin.readline())
for _ in range(n):
query = sys.stdin.readline().strip()
if query.startswith('+'):
# Обычный гоблин встает в конец очереди
_, i = query.split()
right.append(i)
elif query.startswith('*'):
# Привилегированный гоблин встает в середину очереди
_, i = query.split()
# Вставляем в конец первой половины
left.append(i)
elif query == '-':
# Первый гоблин уходит к шаманам
if not left:
# Если первая половина пуста, берем из второй
output.append(right.popleft())
else:
# Иначе берем из первой половины
output.append(left.popleft())
# Балансировка очереди
# Если первая половина меньше второй, перемещаем элемент
if len(left) < len(right):
left.append(right.popleft())
# Если первая половина больше второй, перемещаем элемент
elif len(left) > len(right) + 1:
right.appendleft(left.pop())
# Вывод результатов всех запросов типа '-'
print('\n'.join(output))
if __name__ == "__main__":
main()
Объяснение кода
Задача заключается в управлении очередью гоблинов, где обычные гоблины встают в конец очереди, а привилегированные — в середину. При этом необходимо эффективно обрабатывать три типа запросов:
Добавление обычного гоблина в конец очереди.
Добавление привилегированного гоблина в середину очереди.
Удаление первого гоблина из очереди (он уходит к шаманам).
Основные идеи решения
Использование двух deque
Мы используем две очереди: left и right.
left хранит первую половину очереди, а right — вторую половину.
Это позволяет эффективно вставлять элементы в середину и удалять элементы с начала очереди.
Обработка запросов
Обычный гоблин (+ i):
Добавляется в конец right, так как он должен встать в конец очереди.
Привилегированный гоблин (* i)
Добавляется в конец left, что соответствует середине очереди. Если длина очереди нечётная, он встаёт сразу за центром.
Удаление гоблина (-)
Если left не пуст, удаляем гоблина из начала left.
Если left пуст, удаляем гоблина из начала right.
Балансировка очереди
После каждого запроса проверяем баланс между left и right.
Если left меньше right, перемещаем элемент из начала right в конец left.
Если left больше right более чем на 1, перемещаем элемент из конца left в начало right.
Это гарантирует, что left всегда содержит первую половину очереди, а right — вторую.
Эффективность
Все операции (append, popleft, appendleft, pop) выполняются за O(1), что делает решение эффективным даже для больших значений N (до 10^5).
Пример работы
Рассмотрим пример входных данных:
7
+ 1
+ 2
* 3
+ 4
-
-
-
1. Гоблин 1 встает в конец: left = [], right = [1].
2. Гоблин 2 встает в конец: left = [], right = [1, 2].
3. Привилегированный гоблин 3 встает в середину: left = [3], right = [1, 2].
4. Гоблин 4 встает в конец: left = [3], right = [1, 2, 4].
5. Балансировка: left = [3, 1], right = [2, 4].
6. Первый гоблин (3) уходит: left = [1], right = [2, 4].
7. Первый гоблин (1) уходит: left = [], right = [2, 4].
8. Первый гоблин (2) уходит: left = [], right = [4].
Вывод:
1
3
2
Преимущества решения
Корректность: Решение правильно обрабатывает все типы запросов и поддерживает баланс очереди.
Эффективность: Временная сложность O(1) для каждой операции.
Простота: Код легко читается и понимается благодаря использованию двух deque и балансировки.
Источник решения: hdhai.com
Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Машинки.
Сложность: Сложная.
Статус решения: "Решено".
Условие задачи:
Петя, которому три года, очень любит играть с машинками. Всего у Пети N различных машинок, которые хранятся на полке шкафа так высоко, что он сам не может до них дотянуться. Одновременно на полу комнаты может находиться не более K машинок. Петя играет с одной из машинок на полу и если он хочет поиграть с другой машинкой, которая также находится на полу, то дотягивается до нее сам. Если же машинка находится на полке, то он обращается за помощью к маме. Мама может достать для Пети машинку с полки и одновременно с этим поставить на полку любую машинку с пола. Мама очень хорошо знает своего ребенка и может предугадать последовательность, в которой Петя захочет играть с машинками. При этом, чтобы не мешать Петиной игре, она хочет совершить как можно меньше операций по подъему машинки с пола, каждый раз правильно выбирая машинку, которую следует убрать на полку. Ваша задача состоит в том, чтобы определить минимальное количество операций. Перед тем, как Петя начал играть, все машинки стоят на полке.
Формат ввода (input):
В первой строке содержаться три числа N, K и P (1≤K≤N≤1000001≤K≤N≤100000, 1≤P≤5000001≤P≤500000). В следующих P строках записаны номера машинок в том порядке, в котором Петя захочет играть с ними.
Формат вывода (Output):
Выведите единственное число: минимальное количество операций, которое надо совершить Петиной маме.
Решение:
Python
import sys
import heapq
from collections import defaultdict, deque
def main():
"""Функция main решает задачу минимизации операций для доставания машинок с полки."""
# Считываем входные данные
input_lines = sys.stdin.read().splitlines()
N, K, P = map(int, input_lines[0].split()) # Количество машинок (N), максимальное количество на полу (K), запросов (P)
# Преобразуем последовательность запросов в список
requests = [int(x) for x in input_lines[1:P + 1]]
# Создаем словарь для хранения очередей индексов запросов для каждой машинки
next_use = defaultdict(deque)
for idx, request in enumerate(requests):
next_use[request].append(idx)
# Создаем множество для хранения машинок, которые находятся на полу
on_floor = set()
# Создаем кучу для хранения кортежей (время следующего использования, машинка)
heap = []
# Переменная для подсчета количества операций
operations = 0
# Обрабатываем каждый запрос
for idx, request in enumerate(requests):
# Обновляем очередь следующего использования для текущей машинки
if next_use[request]:
next_use[request].popleft()
if request not in on_floor: # Если нужная машинка не на полу
operations += 1 # Увеличиваем счетчик операций
if len(on_floor) == K: # Если на полу уже находится максимум машинок
# Удаляем машинку, которая будет использована позже всех
_, farthest_car = heapq.heappop(heap)
on_floor.remove(farthest_car)
# Добавляем текущую машинку на пол
on_floor.add(request)
# Обновляем кучу для текущей машинки
if next_use[request]:
heapq.heappush(heap, (-next_use[request][0], request)) # Используем отрицательное время для max-heap
else:
heapq.heappush(heap, (-float('inf'), request)) # Если машинка больше не понадобится
# Выводим результат
print(operations)
# Запускаем функцию main
if __name__ == "__main__":
main()
Объяснение кода
Код решает задачу минимизации количества операций для доставания машинок с полки, используя алгоритм с приоритетной очередью (кучей).
- Считывание входных данных :
N — общее количество различных машинок.K — максимальное количество машинок, которые можно хранить на полу одновременно.P — количество запросов.- Запросы представляют собой последовательность чисел, где каждое число — это индекс машинки, которую нужно достать.
- Подготовка данных :
- Создается словарь
next_use, где для каждой машинки хранится очередь (с помощью deque) индексов её использования в будущем.
- Например, если машинка 3 используется на позициях 5 и 10, то
next_use[3] = deque([5, 10]).
- Инициализация структур данных :
on_floor — множество текущих машинок, находящихся на полу.heap — куча, где хранятся кортежи (время следующего использования, индекс машинки). Используется для отслеживания, какая машинка будет использована позже всех.operations — счетчик операций (сколько раз пришлось доставать машинку с полки).
- Обработка каждого запроса:
- Для каждой машинки из запросов:
- Удаляется текущий индекс использования из очереди
next_use.
- Если машинка уже на полу (
request in on_floor), ничего не делаем.
- Если машинки нет на полу:
- Увеличиваем счетчик операций (
operations += 1).
- Если на полу уже находится максимальное количество машинок (
len(on_floor) == K):
- Удаляем машинку, которая будет использована позже всех. Это делается с помощью
heapq.heappop(heap), который извлекает машинку с максимальным временем следующего использования (благодаря отрицательному значению времени).
- Добавляем текущую машинку на пол (
on_floor.add(request)).
- Обновляем кучу:
- Если машинка еще понадобится, добавляем её в кучу с временем следующего использования.
- Если машинка больше не понадобится, добавляем её в кучу с бесконечным временем (
-float('inf')).
- Вывод результата:
- После обработки всех запросов выводится значение
operations — минимальное количество операций.
Источник решения: hdhai.com
Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Путь спелеолога.
Статус решения: "Решено".
Условие задачи:
Алгоритм. Пещера представлена кубом, разбитым на N частей по каждому измерению (то есть на N3N3 кубических клеток). Каждая клетка может быть или пустой, или полностью заполненной камнем. Исходя из положения спелеолога в пещере, требуется найти, какое минимальное количество перемещений по клеткам ему требуется, чтобы выбраться на поверхность. Переходить из клетки в клетку можно, только если они обе свободны и имеют общую грань.
Решение:
Python
import sys
def main():
"""Функция main решает задачу поиска минимального пути спелеолога к поверхности."""
# Считываем входные данные
input_lines = sys.stdin.read().splitlines() # Читаем все строки из входных данных
N = int(input_lines[0]) # Первое число - размерность пещеры (N)
# Создаем трехмерный массив для представления пещеры
cave = []
current_block = []
for line in input_lines[1:]:
if line.strip() == "": # Если встретилась пустая строка, это разделитель между блоками
if current_block: # Если блок не пустой, добавляем его в пещеру
cave.append(current_block)
current_block = [] # Очищаем текущий блок для следующего уровня
else:
current_block.append(list(line)) # Добавляем строку в текущий блок
# После цикла добавляем последний блок, если он есть
if current_block:
cave.append(current_block)
# Находим начальную позицию спелеолога (S)
start_position = None
for z in range(N):
for y in range(N):
for x in range(N):
if cave[z][y][x] == 'S': # Если нашли символ 'S'
start_position = (z, y, x)
break
if start_position:
break
if start_position:
break
# Инициализируем очередь для BFS (поиск в ширину)
from collections import deque
queue = deque()
queue.append((start_position, 0)) # Кортеж содержит позицию и количество шагов
# Множество посещенных клеток
visited = set()
visited.add(start_position)
# Направления движения (dx, dy, dz) - шесть возможных направлений
directions = [
(0, 0, 1), (0, 0, -1), # Вверх и вниз по z
(0, 1, 0), (0, -1, 0), # Вправо и влево по y
(1, 0, 0), (-1, 0, 0) # Вперед и назад по x
]
# Выполняем поиск в ширину (BFS)
while queue:
(current_z, current_y, current_x), steps = queue.popleft()
# Если достигли верхнего уровня пещеры, то выходим
if current_z == 0 and cave[current_z][current_y][current_x] == '.':
print(steps) # Выводим количество шагов
return
# Проверяем все возможные направления движения
for dz, dy, dx in directions:
new_z, new_y, new_x = current_z + dz, current_y + dy, current_x + dx
# Проверяем, что новые координаты находятся внутри пещеры
if 0 <= new_z < N and 0 <= new_y < N and 0 <= new_x < N:
# Проверяем, что новая клетка свободна и еще не посещена
if cave[new_z][new_y][new_x] != '#' and (new_z, new_y, new_x) not in visited:
visited.add((new_z, new_y, new_x)) # Отмечаем как посещенную
queue.append(((new_z, new_y, new_x), steps + 1)) # Добавляем в очередь с увеличенным количеством шагов
# Запускаем функцию main
if __name__ == "__main__":
main()
Объяснение кода
Ввод данных:Мы считываем все входные данные, разделяя их на строки. Первое число N определяет размерность пещеры. Затем мы создаем трехмерный массив cave, представляющий пещеру, где каждый элемент может быть либо символом # (камень), либо точкой . (пустая клетка), либо буквой S (начальная позиция).
Поиск начальной позиции:
Мы проходим по всем клеткам пещеры, чтобы найти позицию спелеолога (S). Как только она найдена, процесс останавливается.
Поиск в ширину (BFS):
Для поиска минимального пути используется алгоритм BFS. Мы используем очередь, где каждый элемент представляет текущую позицию и количество шагов, сделанных до этой позиции. Мы также используем множество visited для отслеживания уже посещенных клеток, чтобы избежать повторных вычислений.
Направления движения:
Мы определяем шесть возможных направлений движения: вверх, вниз, вправо, влево, вперед и назад. Для каждой клетки проверяем, можно ли переместиться в соседнюю клетку, учитывая границы пещеры и наличие камней.
Условие завершения:
Как только мы достигаем верхнего уровня (z == 0) и попадаем в свободную клетку (.), мы выводим количество шагов и завершаем работу программы.
Этот подход гарантирует, что мы найдем минимальное количество шагов для выхода на поверхность, так как BFS всегда находит кратчайший путь в графе.
Источник решения: hdhai.com