Ctrl K

Самое большое число на бюджет краски

Сложная
Вы рисуете на табло число из цифр от 1 до 9 (ноль рисовать нельзя). На цифру d уходит paint[d - 1] банок краски, любую цифру можно рисовать сколько угодно раз. Нужно потратить **ровно** budget банок. Верните самое большое число, которое можно так нарисовать, в виде строки (оно может быть очень длинным). Если потратить ровно budget нельзя, верните "0".
Пример 1
paint=[4, 4, 4, 4, 4, 4, 4, 3, 5], budget=8 → '98'

Больше двух цифр не получится. Ровно 8 банок дают пары из цифр 1–7 (4 + 4) или 8 и 9 (3 + 5); самое большое из таких чисел — 98.

Пример 2
paint=[1, 5, 5, 5, 5, 5, 5, 5, 2], budget=4 → '1111'

Можно нарисовать 99, 911 или 1111. Длиннее всего — 1111, а более длинное число всегда больше.

Пример 3
paint=[3, 3, 3, 3, 3, 3, 3, 3, 3], budget=7 → '0'

Любая цифра стоит 3, а 7 на 3 не делится — потратить ровно 7 нельзя.

Ограничения
  • len(paint) = 9
  • 1 ≤ paint[i] ≤ 5000
  • 1 ≤ budget ≤ 5000
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиВода между стенами СложнаяСамый большой горящий блок СложнаяПрибыль за две сделки СложнаяВсе способы расставить пробелы СложнаяПереход через пещеру Сложная
загружаем Python…
Вход
paint=[4, 4, 4, 4, 4, 4, 4, 3, 5], budget=8
Ожидается
'98'

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