Question

Сколькими способами Гульназ может разменять 200 тенге монетами достоинством в 1, 5 и 10 тенге?

Answer 1

Ответ:3
200:1
200:5
200:10

Answer 2

Для определения количества способов размена 200 тенге монетами достоинством в 1, 5 и 10 тенге, мы можем воспользоваться методом динамического программирования, известным как "метод размена". Давайте обозначим через dp[i][j] количество способов размена суммы j с использованием первых i типов монет.

Исходя из этого, мы можем использовать следующее рекуррентное соотношение:

cssCopy code
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]

Где coins[i] - это достоинство i-й монеты (1, 5 или 10 тенге).

Сначала создадим таблицу dp размером (3, 201) (так как у нас есть 3 типа монет и нужно разменять 200 тенге):

scssCopy code
dp[0][j] = 0, 0 <= j <= 200  (не можем использовать ни одну монету)
dp[i][0] = 1, 0 <= i <= 2    (единственный способ - не давать сдачу)

Затем заполним таблицу с помощью рекуррентного соотношения:

cssCopy code
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]

Таким образом, dp[2][200] будет содержать искомое количество способов размена 200 тенге монетами достоинством в 1, 5 и 10 тенге.

Итак, давайте выполним вычисления:

scssCopy code
dp[0][j] = 0
dp[i][0] = 1

dp[1][j] = dp[0][j] + dp[1][j - 1]  (j >= 1)
dp[2][j] = dp[1][j] + dp[2][j - 5]  (j >= 5)
dp[2][j] += dp[2][j - 10]           (j >= 10)

Продолжая вычисления, мы можем найти количество способов размена 200 тенге:

cssCopy code
dp[2][200] = dp[1][200] + dp[2][195] + dp[2][190] + ... + dp[2][0]

Вычисления могут быть довольно трудоемкими вручную, но программно можно легко реализовать этот процесс.

Таким образом, количество способов размена 200 тенге монетами достоинством в 1, 5 и 10 тенге будет содержаться в dp[2][200].