Наименьшая сумма выбранных монет

Сумма любого набора из KK монет не меньше суммы KK самых дешёвых. Если дешёвых монет nn, эта минимальная сумма равна aa min⁡(n, K)+b(K−min⁡(n, K))\min(n,\,K)+b(K-\min(n,\,K)). Общая сумма всех монет равна an+b(M−n)an+b(M-n). Поэтому универсальное условие точно равносильно сравнению четырёх минимальных сумм с общей суммой. Проверяем все целые nn от 1 до M−1M-1, со строгим либо нестрогим знаком исходного условия.

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

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

Шаг 1. Сумма любого набора из KK монет не меньше суммы KK самых дешёвых. Если дешёвых монет nn, эта минимальная сумма равна aa min⁡(n, K)+b(K−min⁡(n, K))\min(n,\,K)+b(K-\min(n,\,K)). Общая сумма всех монет равна an+b(M−n)an+b(M-n). Поэтому универсальное условие точно равносильно сравнению четырёх минимальных сумм с общей суммой. Проверяем все целые nn от 1 до M−1M-1, со строгим либо нестрогим знаком исходного условия.
N=400N=400

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

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

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