blocked и два целых числа limit и budget. Нужно выбрать набор различных целых чисел так, чтобы:
- каждое число лежало в отрезке от 1 до limit;
- ни одно число не встречалось в blocked;
- сумма выбранных чисел не превышала budget.
Верните, сколько чисел можно выбрать при этих условиях — как можно больше.
Обратите внимание: limit может достигать миллиарда, так что перебрать все числа по одному не получится.blocked=[2, 5], limit=10, budget=20 → 4
Берём самые маленькие разрешённые числа: 1, 3, 4 и 6 — сумма 14. Следующее, 7, дало бы 21.
blocked=[1], limit=1000000000, budget=1 → 0
Единица запрещена, а любое другое число больше бюджета.
blocked=[3], limit=3, budget=1000000000000000 → 2
len(blocked) ≤ 10⁵blocked[i] ≤ limit ≤ 10⁹budget ≤ 10¹⁸blocked=[2, 5], limit=10, budget=20
4
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 110 тестов на сервере, включая скрытые.