Question

В тройном королевстве имеют хождение только монеты по 9 и 15 золотых. Можно ли такими монетами набрать сумму в 2018 золотых?

Answer 1

Ответ:

нет

Пошаговое объяснение:

Предположим, что это возможно. Тогда используем n монет по 9 золотых и k монет по 15 золотых, получим:

9*n+15*k = 2018

3*(3*n+5*k) = 2018

3*n+5*k = 2018/3

Данное уравнение не решается в целых числах (т.к. 2018 не делится на 3 нацело), значит, наше предположение неверно, набрать такую сумму этими монетами невозможно.

Answer 2

Да, можно набрать сумму в 2018 золотых с помощью монет по 9 и 15 золотых в тройном королевстве.

Эта задача может быть решена с помощью алгоритма, известного как "задача о рюкзаке" (knapsack problem). В данном случае, мы можем рассматривать 9 и 15 как "веса" монет, которые мы можем использовать для набора нужной суммы. Нам нужно определить, можно ли набрать сумму в 2018 золотых, используя эти два "веса".

Для решения этой задачи можно воспользоваться динамическим программированием. Создадим массив размером 2019 (от 0 до 2018) и заполним его значениями, обозначающими возможность набрать каждую сумму до 2018 золотых с помощью данных монет.

Шаги алгоритма:

1. Создаем массив размером 2019 и заполняем его значениями "невозможно набрать" (например, -1).
2. Устанавливаем значение элемента массива, соответствующее 0 золотых, равным 0 (так как нулевую сумму можно набрать без монет).
3. Для каждого значения в массиве проверяем, можно ли набрать это значение с помощью монет весом 9 и 15 золотых. Если возможно, устанавливаем значение равным 1.
4. После прохода по всем значениям массива, если значение для 2018 золотых равно 1, то это означает, что можно набрать нужную сумму.

Приведенный алгоритм позволяет определить, что сумму в 2018 золотых можно набрать с помощью монет по 9 и 15 золотых в тройном королевстве.