40 задач на Python

Пример 2:

Входные данные: 1 3 2 4 5

Выходные данные: 1

Решение:

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

Псевдокод:

ввод номера_домов

подсчет_переездов = 0

если номера_домов[0] == 1 и номера_домов[1] == 2, тогда подсчет_переездов += 1

если номера_домов[1] == 2 и номера_домов[2] == 3, тогда подсчет_переездов += 1

если номера_домов[2] == 3 и номера_домов[3] == 4, тогда подсчет_переездов += 1

если номера_домов[3] == 4 и номера_домов[4] == 5, тогда подсчет_переездов += 1

вывод подсчет_переездов

Реализация на Python:

```python

# Чтение входных данных

house_numbers = list(map(int, input.split))

# Подсчет минимального количества переездов

moves_count = 0

for i in range(4):

if house_numbers[i] == i + 1 and house_numbers[i + 1] == i + 2:

moves_count += 1

# Вывод результата

print(moves_count)

```

Эта задача демонстрирует, как использовать простую логику для определения минимального количества операций, необходимых для достижения определенной цели. Решение основано на анализе текущего расположения жителей и выявлении промежутков, где требуются переезды для выполнения условий задачи.

4. Логическая цепочка чисел

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

Входные данные:

– Последовательность целых чисел, разделенных пробелами.

Выходные данные:

– Если последовательность является логической цепочкой, вывести "YES". Иначе вывести "NO".

Примеры:

Пример 1:

Входные данные: 1 3 6 10 15

Выходные данные: YES

Пример 2:

Входные данные: 2 4 7 12 18

Выходные данные: NO

Решение:

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

Псевдокод:

ввод последовательности_чисел

для каждого i от 1 до длины(последовательности_чисел) – 1:

если последовательность_чисел[i] != последовательность_чисел[i – 1] + i:

вывод "NO"

завершить выполнение

вывод "YES"

Реализация на Python:

```python

# Чтение входных данных

sequence = list(map(int, input.split))

# Проверка на логическую цепочку

for i in range(1, len(sequence)):

if sequence[i] != sequence[i – 1] + i:

print("NO")

break

else:

print("YES")

```

Эта задача иллюстрирует способ проверки последовательности чисел на соответствие логической цепочке. Мы можем пройтись по всей последовательности и проверить выполнение условия для каждой пары чисел. Если условие не выполняется хотя бы для одной пары чисел, мы можем сразу вывести "NO".

5. Тайна древнего лабиринта

Условие задачи: Группа исследователей отправилась исследовать древний лабиринт, о котором ходят легенды. Они обнаружили, что лабиринт состоит из комнат, соединенных таинственными проходами. Каждая комната имеет уникальный номер, а проходы между комнатами двунаправленные. Они обнаружили, что вход в лабиринт находится в комнате с номером 1, а выход – в комнате с номером N.

Каждый проход имеет определенную стоимость прохождения, которая может быть как положительной, так и отрицательной. Исследователи хотят найти путь с минимальной суммарной стоимостью прохождения из комнаты 1 в комнату N.

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

Входные данные:

– Первая строка содержит два целых числа: N (2 <= N <= 10^5) – количество комнат, и M (1 <= M <= 2*10^5) – количество проходов между комнатами.

– Следующие M строк содержат описание проходов. Каждая строка содержит три целых числа: a, b и w (1 <= a, b <= N, -10^3 <= w <= 10^3), где a и b – номера комнат, соединенных проходом, а w – стоимость прохождения этого прохода.

Выходные данные:

– Одно целое число – минимальная суммарная стоимость прохождения из комнаты 1 в комнату N. Если путь не существует, вывести -1.

Примеры:

Пример 1:

Входные данные:

5 7

1 2 4

1 3 2

2 3 5

2 4 10

3 4 -3

3 5 3

4 5 4

Выходные данные: 6

Пример 2:

Входные данные:

3 2

1 2 1

2 3 1

Выходные данные: 2

Решение:

Для нахождения минимальной суммарной стоимости прохождения лабиринта из комнаты 1 в комнату N мы можем воспользоваться алгоритмом поиска кратчайшего пути в графе. Мы будем использовать алгоритм Дейкстры для нахождения кратчайшего пути от вершины 1 до вершины N.

Псевдокод:

ввод N, M

инициализация графа G

для каждого i от 1 до M:

ввод a, b, w

добавить ребро (a, b) со стоимостью w в граф G

вызвать алгоритм Дейкстры для поиска кратчайшего пути от вершины 1 до вершины N в графе G

вывод результат

Реализация на Python:

```python

import heapq

def dijkstra(graph, start, end):

pq = [(0, start)]

distances = {v: float('inf') for v in graph}

distances[start] = 0

while pq:

dist, node = heapq.heappop(pq)