ML Mentor
К собеседованиям
Т-Банк

Алгоритмический тренажер

Алгоритмическая секция в Т-Банк

Тип тренировки
Алгоритмы
Задач
3
Компания
Т-Банк
Дата
2025-10-07
Задача 1MediumЖадный алгоритмСортировкаМассивыКупоны

Минимальная стоимость после купонов

Условие задачи

Дан список цен товаров prices, количество купонов k и размер скидки x.

Каждый купон можно применить к одному товару. Один купон уменьшает цену выбранного товара на x, но цена не может стать отрицательной. Купоны можно применять к одному и тому же товару несколько раз.

Верните минимальную сумму денег, которую придется заплатить за все товары после применения не более k купонов.

Сигнатура

def min_total_after_coupons(prices: list[int], k: int, x: int) -> int:

Ваше решение

Консоль
Нажмите «Запустить проверки» или Ctrl+Enter

Идея решения

Жадность состоит из двух фаз.

Сначала выгодно применять купоны к полным блокам размера x: если товар стоит a, то можно применить a // x купонов и уменьшить цену без выбора между товарами. Ограничиваем это число оставшимся k.

После этой фазы все остатки меньше x. Каждый следующий купон может занулить один остаток, поэтому нужно выбрать самые большие остатки и занулить их первыми.

Если купонов после первой фазы больше или равно числу оставшихся положительных товаров, ответ равен нулю.

Оцените сложность
Открыть задачу в тренажере
Задача 2MediumБинарный поискМассивыГраницы

Первое и последнее вхождение в отсортированном массиве

Дан отсортированный по неубыванию массив nums и число target.

Верните индексы первого и последнего вхождения target. Если числа в массиве нет, верните пустой список.

Решение должно работать за O(log n).

Сигнатура

def search_range(nums: list[int], target: int) -> list[int]:

Ваше решение

Консоль
Нажмите «Запустить проверки» или Ctrl+Enter

Идея решения

Нужно найти границы, а не просто любое вхождение.

Пишем функцию lower_bound(value), которая возвращает первый индекс, где nums[i] >= value. Тогда:

  • left = lower_bound(target)
  • right_exclusive = lower_bound(target + 1)

Если left вышел за массив или nums[left] != target, числа нет. Иначе ответ [left, right_exclusive - 1].

Для общего случая без предположений о диапазоне чисел можно искать upper_bound(target): первый индекс, где nums[i] > target.

Оцените сложность
Открыть задачу в тренажере
Задача 3MediumГеометрияХеш-множествоСимметрияМассивы

Ось симметрии для точек

Условие задачи

Даны различные точки на плоскости с целыми координатами.

Нужно определить, существует ли вертикальная ось симметрии, то есть прямая x = c, параллельная оси y, относительно которой множество точек совпадает само с собой.

Если такая ось есть, верните ее абсциссу c. Если оси нет, верните None.

Сигнатура

def vertical_symmetry_axis(points: list[list[int]]):

Ваше решение

Консоль
Нажмите «Запустить проверки» или Ctrl+Enter

Идея решения

Если множество симметрично относительно вертикальной оси, то самая левая и самая правая точки по x должны переходить друг в друга. Поэтому удвоенная абсцисса оси равна:

axis2 = min_x + max_x

Храним все точки в set. Для каждой точки (x, y) отраженная точка должна иметь координаты (axis2 - x, y). Если хотя бы одной такой точки нет, вертикальной оси симметрии не существует.

Удобно хранить именно axis2, чтобы не ошибаться на полуцелых осях: например, для точек с x=0 и x=3 ось равна 1.5.

Оцените сложность
Открыть задачу в тренажере