Ctrl K

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

Средняя
Длинные последовательности с повторами удобно хранить сжатыми: пара [value, count] означает, что число value идёт подряд count раз. Например, [[7, 2], [4, 3]] — это [7, 7, 4, 4, 4]. Даны две сжатые последовательности first и second. В развёрнутом виде они одинаковой длины. Перемножьте их поэлементно (i-й элемент на i-й) и верните результат тоже в сжатом виде. Сжатие должно быть самым коротким: два соседних куска с одинаковым значением объединяются в один. Разворачивать последовательности целиком не стоит — в развёрнутом виде они могут быть очень длинными.
Пример 1
first=[[2, 4]], second=[[3, 1], [5, 3]] → [[6, 1], [10, 3]]

Развернём: [2, 2, 2, 2] и [3, 5, 5, 5]. Произведения: [6, 10, 10, 10], то есть одна шестёрка и три десятки.

Пример 2
first=[[1, 2], [3, 2]], second=[[6, 2], [2, 2]] → [[6, 4]]

Получается [6, 6, 6, 6]. Соседние одинаковые куски надо слить в один: [[6, 4]], а не [[6, 2], [6, 2]].

Ограничения
  • 1 ≤ len(first), len(second) ≤ 10⁵
  • Каждый элемент — пара [value, count], 1 ≤ value, count ≤ 10⁴
  • Развёрнутые последовательности одинаковой длины
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиДве доски и вода СредняяТройки с нулевой суммой СредняяСумма тройки ближе всего к цели СредняяЧетыре числа с заданной суммой СредняяСледующая расстановка по порядку Средняя
загружаем Python…
Вход
first=[[2, 4]], second=[[3, 1], [5, 3]]
Ожидается
[[6, 1], [10, 3]]

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