У вас есть \(5\) различных типов монет, каждый из которых имеет значение равное одному из первых \(5\) треугольных чисел: \(1\), \(3\), \(6\), \(10\) и \(15\). Все типы монет имеются в неограниченном количестве. Ваша задача — определить, какого минимального количества монет достаточно, чтобы набрать сумму ровно \(n\).
Можно показать, что ответ всегда существует.
Примечание
В первом наборе тестовых данных, где \(n = 1\), ответ \(1\), поскольку достаточно использовать одну монету стоимости \(1\). \(1 = 1 \cdot 1\).
В четвертом наборе входных данных, где \(n = 5\), ответ \(3\), который может быть достигнут, используя две монеты стоимости \(1\) и одну монету стоимости \(3\). \(5 = 2 \cdot 1 + 1 \cdot 3\).
В седьмом наборе входных данных, где \(n = 12\), ответ \(2\), который может быть достигнут, используя две монеты стоимости \(6\).
В девятом наборе входных данных, где \(n = 16\), ответ \(2\), который может быть достигнут, используя одну монету стоимости \(1\) и одну монету стоимости \(15\). Альтернативным решением может быть использование одной монеты стоимости \(10\) и одной монеты стоимости \(6\). \(16 = 1 \cdot 1 + 1 \cdot 15 = 1 \cdot 6 + 1 \cdot 10\).