Ctrl K

Подтянуть числа под делители

Сложная
Даны список values и короткий список divisors. За один шаг можно увеличить любое число из values на 1. Нужно, чтобы для каждого d из divisors в values нашлось хотя бы одно число, которое делится на d. Одно и то же число может «закрывать» сразу несколько делителей. Верните наименьшее число шагов, за которое этого можно добиться.
Пример 1
values=[7, 13], divisors=[3, 4] → 3

Поднимаем 7 до 9 (делится на 3) и 13 до 16 (делится на 4): 2 + 3 = 5. Можно и 13 до 15 (на 3), 7 до 8 (на 4): 2 + 1 = 3 — это лучше. Поднять одно число до 12 (делится на оба) стоит не меньше 5.

Пример 2
values=[5, 9], divisors=[6, 3] → 1

Достаточно поднять 5 до 6: оно делится и на 6, и на 3.

Пример 3
values=[10, 1], divisors=[5] → 0
Ограничения
  • 1 ≤ len(values) ≤ 5·10⁴
  • 1 ≤ len(divisors) ≤ 4, len(divisors) ≤ len(values)
  • 1 ≤ values[i], divisors[j] ≤ 10⁴
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиДве группы с одинаковым средним СложнаяЦепочки с квадратными суммами СложнаяПроизведение различных простых СложнаяМеньше всего прямых через точки СредняяПроизведения без квадратов Средняя
загружаем Python…
Вход
values=[7, 13], divisors=[3, 4]
Ожидается
3

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