Ctrl K

k-я сумма марками одного номинала

Сложная
На почте есть марки нескольких номиналов — массив stamps, все номиналы разные. Марок каждого номинала сколько угодно, но на один конверт клеят марки только одного номинала: например, три марки по 4 дают 12, а марки 4 и 6 вместе — нельзя. Выпишем все суммы, которые можно так оплатить, без повторов и по возрастанию. Верните k-ю из них (нумерация с единицы).
Пример 1
stamps=[4, 6], k=5 → 16

Марками по 4 можно оплатить 4, 8, 12, 16, …, марками по 6 — 6, 12, 18, … Вместе получаются суммы 4, 6, 8, 12, 16, 18, … — пятая из них 16.

Пример 2
stamps=[7, 3, 5], k=6 → 10

Доступные суммы: 3, 5, 6, 7, 9, 10, … — шестая равна 10.

Пример 3
stamps=[2], k=1000000000 → 2000000000
Ограничения
  • 1 ≤ len(stamps) ≤ 15
  • 1 ≤ stamps[i] ≤ 25
  • все номиналы в stamps различны
  • 1 ≤ k ≤ 2 · 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиНОД пар по номеру в сортировке СложнаяНОД, умноженный на сумму СложнаяПодтянуть числа под делители СложнаяПотерянный билет ЛёгкаяN-е число, кратное одному из трёх Средняя
загружаем Python…
Вход
stamps=[4, 6], k=5
Ожидается
16

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