Codeforces Round 931 (Div. 2) |
---|
Закончено |
У вас есть $$$5$$$ различных типов монет, каждый из которых имеет значение равное одному из первых $$$5$$$ треугольных чисел: $$$1$$$, $$$3$$$, $$$6$$$, $$$10$$$ и $$$15$$$. Все типы монет имеются в неограниченном количестве. Ваша задача — определить, какого минимального количества монет достаточно, чтобы набрать сумму ровно $$$n$$$.
Можно показать, что ответ всегда существует.
В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В единственной строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$1 \leq n \leq 10^9$$$) — требуемое значение.
Для каждого набора входных данных выведите одно число — минимальное необходимое число монет.
14123571112141617182098402931328
1 2 1 3 2 2 2 3 2 3 2 2 8 26862090
В первом наборе тестовых данных, где $$$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$$$.
Название |
---|