Раздельная оплата монетами

Последовательность применённых правил и переходов в пунктах задачи.

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

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Количество монет каждого номинала
  2. Раздельная оплата

    Сначала: Количество монет каждого номинала

  3. Ответ: да

    Сначала: Раздельная оплата

  4. Количество монет каждого номинала

    Сначала: Ответ: да

  5. Раздельная оплата

    Сначала: Количество монет каждого номинала

  6. Ответ: нет

    Сначала: Раздельная оплата

  7. Количество монет каждого номинала

    Сначала: Ответ: нет

  8. Минимум монет нужного номинала

    Сначала: Количество монет каждого номинала

  9. Ответ

    Сначала: Минимум монет нужного номинала

Разобранный пример

Известно, что в кошельке лежало nn монет, каждая из которых могла иметь достоинство 2, 5 и 10 рублей. Аня сделала все свои покупки, расплатившись за каждую покупку отдельно без сдачи только этими монетами, потратив при этом все монеты из кошелька.

а) Могли ли все её покупки состоять из блокнота за 56 рублей и ручки за 29 рублей, если nn = 14?

б) Могли ли её покупки состоять из чашки чая за 10 рублей, сырка за 15 рублей и пирожка за 20 рублей, если nn = 19?

в) Какое наименьшее количество пятирублёвых монет могло быть в кошельке, если Аня купила только альбом за 85 рублей и nn = 24?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Для цены PP количество монет каждого номинала dd находится между 0 и ⌊Pd⌋\left\lfloor \frac{P}{d}\right\rfloor. Перебираем все неотрицательные тройки количеств и оставляем ровно те, для которых 2x+5y+10z=P2x+5y+10z=P. Это полная конечная область способов оплаты без сдачи.
n=14n=14
T=(56;29)\mathcal T=\left(56;29\right)
Шаг 2. Для каждой покупки независимо выбираем одну допустимую тройку. Затем складываем количества монет и оставляем варианты с заданным общим количеством nn. В таблице указаны способы оплаты каждой покупки в одном подходящем варианте; пустая таблица означает, что подходящих вариантов нет.
T=(((3;0;5);(2;3;1)))\mathcal T=\left(\left(\left(3;0;5\right);\left(2;3;1\right)\right)\right)
Шаг 3. Да. Приведённая конструкция удовлетворяет всем требованиям.
Шаг 1. Для цены PP количество монет каждого номинала dd находится между 0 и ⌊Pd⌋\left\lfloor \frac{P}{d}\right\rfloor. Перебираем все неотрицательные тройки количеств и оставляем ровно те, для которых 2x+5y+10z=P2x+5y+10z=P. Это полная конечная область способов оплаты без сдачи.
n=19n=19
T=(10;15;20)\mathcal T=\left(10;15;20\right)
Шаг 2. Для каждой покупки независимо выбираем одну допустимую тройку. Затем складываем количества монет и оставляем варианты с заданным общим количеством nn. В таблице указаны способы оплаты каждой покупки в одном подходящем варианте; пустая таблица означает, что подходящих вариантов нет.
T={}\mathcal T=\left\{\right\}
Шаг 3. Нет. Необходимое и достаточное условие либо полная конечная область исключает такой случай.
Шаг 1. Для цены PP количество монет каждого номинала dd находится между 0 и ⌊Pd⌋\left\lfloor \frac{P}{d}\right\rfloor. Перебираем все неотрицательные тройки количеств и оставляем ровно те, для которых 2x+5y+10z=P2x+5y+10z=P. Это полная конечная область способов оплаты без сдачи.
n=24n=24
T=(85)\mathcal T=\left(85\right)
Шаг 2. Для единственной покупки оставляем тройки с нужной ценой и общим количеством монет. Сравниваем количество пятирублёвых монет во всех оставшихся тройках. Приведённая тройка достигает найденного минимума.
T=((15;7;2))\mathcal T=\left(\left(15;7;2\right)\right)
Шаг 3. Записываем найденное значение.
77

Открыть задачу целиком

Попробовать самостоятельно