Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Увлекательная игра.
Сложность: Средняя.
Статус решения: "Решено".
Условие задачи:
Петя и Маша играют в увлекательную игру. Маша загадывает число от 1 до n, записывает его на чистый тетрадный лист, кладёт в конверт и запечатывает. После этого Петя пытается это число отгадать. Он может задавать любые вопросы про это число: «Верно ли, что это число равно трем?», «Верно ли, что это число — число Фибоначчи?», «Верно ли, что это число простое?» и так далее. Получив ответ «да», Петя отдает Маше a конфет, а в случае ответа «нет» — b конфет.
В какой-то момент Петя произносит сакраментальную фразу: «Я знаю, что это за число». После этого они распечатывают конверт в присутствии свидетелей, убеждаются в Петиной правоте, и Маша получает внушительную порцию конфет, а Петя — моральное удовлетворение.
Петя очень любит играть в эту игру, но его кондитерские запасы ограничены. Поэтому Петя хочет выяснить, какое минимальное количество конфет может ему потребоваться, чтобы отгадать Машино число в худшем случае. Помогите Пете найти указанный минимум.
Формат ввода (input):
Входной файл содержит три целых числа: n (1≤n≤10001≤n≤1000), a и b (0≤a,b≤1060≤a,b≤106)
Формат вывода (Output):
Выведите одно число — минимальное количество конфет, которое должен иметь Петя, чтобы отгадать Машино число в худшем случае.
Решение:
Python
import sys
def main():
"""
Функция для решения задачи о минимальном количестве конфет.
"""
# Чтение входных данных: n, a, b
n, a, b = map(int, sys.stdin.read().split())
# Создаем массив dp, где dp[i] — минимальное количество конфет,
# необходимое для угадывания числа из i вариантов в худшем случае.
dp = [0] * (n + 1)
# Базовый случай: если есть только одно число, то конфет не нужно.
dp[1] = 0
# Заполняем массив dp для всех значений от 2 до n.
for i in range(2, n + 1):
# Инициализируем dp[i] как максимально возможное значение.
dp[i] = float('inf')
# Перебираем все возможные вопросы Пети.
for j in range(1, i):
# Если Петя задает вопрос, разделяющий множество чисел на две группы:
# - группа размера j (ответ "да"),
# - группа размера i - j (ответ "нет").
# Тогда в худшем случае потребуется max(dp[j], dp[i - j]) конфет
# плюс стоимость ответа "да" или "нет".
cost_yes = dp[j] + a # Стоимость, если ответ "да"
cost_no = dp[i - j] + b # Стоимость, если ответ "нет"
# В худшем случае выбираем максимальную из двух стоимостей.
worst_case_cost = max(cost_yes, cost_no)
# Минимизируем общую стоимость для i чисел.
dp[i] = min(dp[i], worst_case_cost)
# Выводим минимальное количество конфет для n чисел.
print(dp[n])
if __name__ == "__main__":
main()
Объяснение кода
Постановка задачи и идея решения:
Задача заключается в том, чтобы определить минимальное количество конфет, которые потребуются Пете для гарантированного угадывания числа, загаданного Машей, при условии, что он может задавать вопросы, делящие множество чисел на две группы. Каждый вопрос имеет "стоимость" в зависимости от ответа ("да" или "нет").
Основная идея решения заключается в использовании динамического программирования . Мы строим массив dp, где dp[i] обозначает минимальное количество конфет, необходимых для угадывания числа из i возможных вариантов.
Базовый случай:
Если есть только одно число (i = 1), то Петя уже знает ответ, и ему не нужно задавать никаких вопросов. Таким образом, dp[1] = 0.
Рекуррентное соотношение:
Для каждого числа i > 1 мы перебираем все возможные способы разделения множества чисел на две группы:
Группа размера j (ответ "да"),
Группа размера i - j (ответ "нет").
Стоимость для каждого разделения вычисляется как:
cost_yes = dp[j] + a — если ответ "да",
cost_no = dp[i - j] + b — если ответ "нет".
В худшем случае выбирается максимальная из этих двух стоимостей:
worst_case_cost = max(cost_yes, cost_no)
Мы минимизируем эту стоимость по всем возможным разделениям:
dp[i] = min(dp[i], worst_case_cost)
Вычислительная сложность:
Внешний цикл проходит по всем значениям от 2 до n (итераций: O(n)).
Внутренний цикл перебирает все возможные разделения для текущего i (итераций: O(i)).
Таким образом, общая сложность алгоритма составляет O(n^2) , что приемлемо для ограничений задачи (n ≤ 1000).
Источник решения: hdhai.com
Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: 3Sum Closest.
Сложность: Средняя.
Статус решения: "Решено".
Условие задачи:
Дан массив целых чисел nums длины n и целое число target. Найдите три числа в массиве nums, сумма которых наиболее близка к target. Верните сумму этих трех чисел. Можно предположить, что для каждого входного набора существует ровно одно решение.
Решение:
Python
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
# Сначала сортируем массив для удобства поиска
nums.sort() # Сортировка позволяет использовать метод двух указателей
# Инициализируем переменную для хранения ближайшей суммы
closest_sum = float('inf') # Бесконечность как начальное значение
# Проходим по каждому элементу массива, рассматривая его как первый элемент тройки
for i in range(len(nums) - 2): # До len(nums) - 2, так как нужны еще два элемента
left, right = i + 1, len(nums) - 1 # Указатели на два других элемента
while left < right: # Пока указатели не встретились
current_sum = nums[i] + nums[left] + nums[right] # Текущая сумма трех элементов
# Если текущая сумма ближе к цели, чем предыдущая ближайшая сумма, обновляем её
if abs(current_sum - target) < abs(closest_sum - target):
closest_sum = current_sum
# Двигаем указатели в зависимости от того, больше или меньше текущая сумма цели
if current_sum < target:
left += 1 # Увеличиваем левый указатель, чтобы увеличить сумму
elif current_sum > target:
right -= 1 # Уменьшаем правый указатель, чтобы уменьшить сумму
else:
# Если текущая сумма равна цели, возвращаем её сразу (она оптимальна)
return current_sum
# Возвращаем ближайшую сумму после завершения цикла
return closest_sum
Объяснение кода
Сортировка массива:
Мы начинаем с сортировки массива nums. Это необходимо для того, чтобы можно было эффективно использовать метод двух указателей. Сортировка позволяет нам легко регулировать сумму, двигая указатели влево или вправо.
Инициализация переменной closest_sum:
Переменная closest_sum используется для хранения текущей ближайшей суммы к целевому значению target. Начальное значение задается как бесконечность (float('inf')), чтобы любая реальная сумма была ближе к цели.
Основной цикл:
Мы проходим по каждому элементу массива, рассматривая его как первый элемент тройки. Для каждого такого элемента мы используем два указателя (left и right) для поиска двух других элементов.
Метод двух указателей:
Указатель left начинается сразу после текущего элемента i, а указатель right начинается с конца массива.
Мы вычисляем текущую сумму трех элементов (current_sum) и проверяем, насколько она близка к целевому значению target.
Если текущая сумма ближе к цели, чем ранее найденная ближайшая сумма, мы обновляем closest_sum.
Движение указателей:
Если текущая сумма меньше цели, мы увеличиваем левый указатель (left += 1), чтобы увеличить сумму.
Если текущая сумма больше цели, мы уменьшаем правый указатель (right -= 1), чтобы уменьшить сумму.
Если текущая сумма равна цели, мы немедленно возвращаем её, так как это оптимальное решение.
Возврат результата:
После завершения всех итераций возвращается значение closest_sum, которое представляет собой сумму трех чисел, наиболее близкую к целевому значению.
Пример работы программы:
Входные данные:
nums = [-1, 2, 1, -4]
target = 1
Выходные данные: 2
Источник решения: hdhai.com
Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: 3Sum.
Сложность: Средняя.
Статус решения: "Решено".
Условие задачи:
Дан массив целых чисел "nums". Необходимо вернуть все возможные тройки элементов "[nums[i], nums[j], nums[k]]", такие что:
- Индексы удовлетворяют условиям: $i \neq j$, $i \neq k$ и $j \neq k$.
- Сумма элементов тройки равна нулю: $nums[i] + nums[j] + nums[k] = 0$.
Обратите внимание, что набор решений не должен содержать повторяющихся троек.
Решение:
Python
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# Сортируем массив для удобства поиска и исключения дубликатов
nums.sort()
result = [] # Результирующий список для хранения троек
# Проходим по каждому элементу массива
for i in range(len(nums)):
# Если текущий элемент больше нуля, то сумма трех чисел не может быть равна нулю,
# так как массив отсортирован и все последующие элементы будут положительными
if nums[i] > 0:
break
# Пропускаем дубликаты текущего элемента
if i > 0 and nums[i] == nums[i - 1]:
continue
# Инициализируем два указателя для поиска пары чисел
left, right = i + 1, len(nums) - 1
# Пока левый указатель меньше правого
while left < right:
total = nums[i] + nums[left] + nums[right] # Вычисляем сумму трех чисел
if total == 0: # Если сумма равна нулю
result.append([nums[i], nums[left], nums[right]]) # Добавляем тройку в результат
# Пропускаем дубликаты для левого указателя
while left < right and nums[left] == nums[left + 1]:
left += 1
# Пропускаем дубликаты для правого указателя
while left < right and nums[right] == nums[right - 1]:
right -= 1
# Двигаем оба указателя к центру
left += 1
right -= 1
elif total < 0: # Если сумма меньше нуля, двигаем левый указатель вправо
left += 1
else: # Если сумма больше нуля, двигаем правый указатель влево
right -= 1
return result # Возвращаем результирующий список троек
Объяснение кода
Сортировка массива:
Мы начинаем с сортировки массива nums. Это позволяет нам эффективно использовать метод двух указателей и избегать дубликатов.
Основной цикл:
Мы перебираем каждый элемент массива (nums[i]) и рассматриваем его как первый элемент потенциальной тройки.
Если текущий элемент больше нуля, мы завершаем цикл, так как сумма трех положительных чисел не может быть равна нулю.
Пропуск дубликатов:
Чтобы избежать повторяющихся троек, мы пропускаем одинаковые значения для первого элемента тройки (nums[i]).
Два указателя:
Для каждого выбранного nums[i], мы инициализируем два указателя: left (начинается с i + 1) и right (начинается с конца массива).
Мы вычисляем сумму трех чисел (nums[i] + nums[left] + nums[right]):
Если сумма равна нулю, добавляем тройку в результат и двигаем оба указателя, пропуская дубликаты.
Если сумма меньше нуля, увеличиваем левый указатель (left), чтобы увеличить сумму.
Если сумма больше нуля, уменьшаем правый указатель (right), чтобы уменьшить сумму.
Возврат результата:
После завершения всех итераций возвращаем список уникальных троек.
Пример выполнения:
Входные данные:
nums = [-1, 0, 1, 2, -1, -4]
Выходные данные:
[[-1, -1, 2], [-1, 0, 1]]
Источник решения: hdhai.com