Все суммы после добавления единичных монет

Вычислим множество BB всех сумм ax+byax+by в доказанных границах и оставим суммы от 0 до требуемой верхней границы TT. Если добавлено kk монет по 1, каждая сумма vv из BB даёт все целые значения от vv до v+kv+k. Чтобы эти промежутки покрыли от 0 до TT, необходимо и достаточно k≥vnext−v−1k\geq v_{n}ext-v-1 для любых соседних сумм и k≥T−vmax⁡k\geq T-v_{\max}. Поэтому минимум kk равен максимуму этих разрывов и остатка в конце. Это одновременно нижняя граница и доказательство покрытия всех сумм.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что нужно знать

Применение в задаче

Шаг 1. Вычислим множество BB всех сумм ax+byax+by в доказанных границах и оставим суммы от 0 до требуемой верхней границы TT. Если добавлено kk монет по 1, каждая сумма vv из BB даёт все целые значения от vv до v+kv+k. Чтобы эти промежутки покрыли от 0 до TT, необходимо и достаточно k≥vnext−v−1k\geq v_{n}ext-v-1 для любых соседних сумм и k≥T−vmax⁡k\geq T-v_{\max}. Поэтому минимум kk — максимум этих разрывов и остатка в конце. Это одновременно нижняя граница и доказательство покрытия всех сумм.
Δmax⁡=1\Delta_{\max}=1
T−bmax⁡=3T-b_{\max}=3

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу