Добавление рублёвых монет

Если добавлено cc рублёвых монет, каждая исходно достижимая сумма vv даёт все целые суммы от vv до v+cv+c. Проверяем покрытие требуемого отрезка этими промежутками. Достаточно 0≤c≤H0\leq c\leq H, где HH обозначает правую границу отрезка: HH рублёвых монет заведомо хватает. Первая подходящая величина cc является минимумом.

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

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

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

Шаг 2. Если добавлено cc рублёвых монет, каждая исходно достижимая сумма vv даёт все целые суммы от vv до v+cv+c. Проверяем покрытие требуемого отрезка этими промежутками. Достаточно 0≤c≤H0\leq c\leq H, где HH — правая граница отрезка: HH рублёвых монет заведомо хватает. Первая подходящая величина cc является минимумом.
T=((0;1);(1;179);(2;180);(3;0))\mathcal T=\left(\left(0;1\right);\left(1;179\right);\left(2;180\right);\left(3;0\right)\right)

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

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

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