Условия любых выбранных монет

Пусть количества номиналов равны xx, yy, zz. Условие, что среди любых KK монет есть данный номинал, равносильно тому, что монет остальных двух номиналов не больше K−1K-1. Это верно и тогда, когда всех монет меньше KK: плохой набор просто не существует. Получаем три попарных ограничения. Их сумма ограничивает общее количество; каждое количество также ограничено минимумом двух правых частей. Перебираем все положительные целые количества: каждый из трёх номиналов имеется по условию. Используем количества в этих доказанных границах и, если указано, учитываем минимальное общее количество.

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

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

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

Шаг 1. Пусть количества номиналов равны xx, yy, zz. Условие, что среди любых KK монет есть данный номинал, равносильно тому, что монет остальных двух номиналов не больше K−1K-1. Это верно и тогда, когда всех монет меньше KK: плохой набор просто не существует. Получаем три попарных ограничения. Их сумма ограничивает общее количество; каждое количество также ограничено минимумом двух правых частей. Перебираем все положительные целые количества: каждый из трёх номиналов имеется по условию. Используем количества в этих доказанных границах и, если указано, учитываем минимальное общее количество.

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

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

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