Сегодня Али в местном магазине сделал покупку за C тенге. Он только хотел расплатится и услышал от продавца фразу "Без сдачи пожалуйста, молодой человек". У него есть всего N монет достоинств a1, a2, ..., aN тенге.
Определите, сможет ли он расплатится без сдачи.

Для того чтобы Али мог расплатиться без сдачи, необходимо проверить, возможно ли с помощью его монет собрать точную сумму $C$ тенге.

Задача сводится к следующему: если у Али есть набор монет достоинств $a_1, a_2, \ldots, a_N$, то нужно определить, существует ли комбинация этих монет, сумма которых точно равна $C$. Это классическая задача о рюкзаке, также известная как задача о сумме подмножеств.

Подход к решению задачи

1. Проверка на тривиальные случаи:

   • Если сумма всех монет меньше $C$, то ответ однозначно "нет", так как даже если использовать все монеты, нужную сумму не набрать.
   • Если сумма всех монет равна $C$, то ответ однозначно "да", так как можно использовать все монеты.

2. Использование динамического программирования:

   • Создадим булевый массив $dp$ длиной $C + 1$, где $dp[x]$ будет означать, можно ли набрать сумму $x$ тенге с помощью имеющихся монет.
   • Инициализируем массив так: $dp[0] = \text{true}$, потому что сумма 0 всегда достижима (ничего не выбирая).
   • Для каждой монеты $a_i$ и для каждой суммы $x$ от $C$ до $a_i$ (в обратном порядке) проверяем: если сумма $x - a_i$ достижима, то и сумма $x$ становится достижимой, то есть $dp[x] = \text{true}$.

3. Вывод результата:

   • После обработки всех монет проверяем значение $dp[C]$. Если $dp[C] = \text{true}$, значит Али сможет расплатиться без сдачи, иначе — нет.

Пример алгоритма

Рассмотрим пример, когда:

• $C = 10$ тенге.
• $N = 3$ монеты с номиналами $2$, $3$, и $5$ тенге.

Алгоритм будет работать следующим образом:

• Инициализация: $dp[0] = \text{true}$, остальные значения в массиве $dp$ — false.
• Рассматриваем первую монету (2 тенге):
  • Обновляем $dp$ так, что теперь возможны суммы $2, 4, 6, 8,$ и $10$ тенге.
• Рассматриваем вторую монету (3 тенге):
  • Теперь к предыдущим значениям добавляются возможные суммы $3, 5, 7, 9$, и $10$ тенге.
• Рассматриваем третью монету (5 тенге):
  • Добавляются суммы $5, 7, 8, 10$.
• Проверяем $dp[10]$: оно будет равно true, значит, Али сможет расплатиться без сдачи.

Временная сложность

Этот подход работает за $O(N \times C)$, где $N$ — количество монет, а $C$ — требуемая сумма. Такой подход подходит для умеренных значений $N$ и $C$, например, если $C$ не превышает нескольких тысяч.

Итог

Если после выполнения алгоритма $dp[C] = \text{true}$, то ответ "да" — Али сможет расплатиться без сдачи. Если $dp[C] = \text{false}$, то ответ "нет" — Али не сможет оплатить точную сумму.