Олимпиадная информатика

события, задачи, тесты, решения, комментарии

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Задача 14-1. Монетки
(Разбор)

Представим N в виде суммы слагаемых вида A_K*b_K, где А_K - достоинство монеты с номером K, а b_K - количество монет с таким достоинством. По условию задачи 0<=b_K<=2, значит всего вариантов 3^M. Перебрать эти варианты можно с помощью рекурсивного алгоритма, заметив, что если мы возьмем b_M монет достоинства А_M, то задача сведется к аналогичной, где используются монеты достоинствами A₁, A₂,..., A_M-1 и требуется набрать сумму N-A_M*b_M.