Ctrl K

Отрезок зацикленного плейлиста

Средняя
Плейлист tracks поставлен на повтор: после последнего трека снова играет первый, и так бесконечно. tracks[i] — длительность i-го трека. Нужно выбрать несколько подряд идущих треков этой бесконечной ленты так, чтобы их суммарная длительность была ровно total. Верните наименьшее число треков в таком отрезке или -1, если подобрать его нельзя.
Пример 1
tracks=[4, 2, 5], total=9 → 2

Плейлист крутится по кругу: 4, 2, 5, 4, 2, 5, … Подряд идущие 5 и 4 дают 9 — это два трека.

Пример 2
tracks=[3, 1], total=10 → -1

Треки чередуются: 3, 1, 3, 1, … Отрезок чётной длины даёт сумму, кратную 4, а нечётной — нечётную сумму. Сумма 10 недостижима.

Пример 3
tracks=[2, 2, 3], total=14 → 6

Два полных круга — ровно 14, это шесть треков.

Ограничения
  • 1 ≤ len(tracks) ≤ 10⁵
  • 1 ≤ tracks[i] ≤ 10⁵
  • 1 ≤ total ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОкна с заданным числом тревог СредняяОтрезки с k нечётными СредняяСнять с краёв ровно столько СредняяСамый короткий рывок СредняяСамый длинный отрезок с заданной суммой Средняя
загружаем Python…
Вход
tracks=[4, 2, 5], total=9
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 117 тестов на сервере, включая скрытые.