#P1092. 硬币问题

硬币问题

题目描述

今有面值为 1、5、11 元的硬币各无限枚。

想要凑出 nn 元,问需要的最少硬币数量。

输入格式

仅一行,一个正整数 nn

输出格式

仅一行,一个正整数,表示需要的硬币个数。

样例 #1

样例输入 #1

15

样例输出 #1

3

样例 #2

样例输入 #2

12

样例输出 #2

2

提示

样例解释

对于样例数据 1,最佳方案是 15=5+5+515=5+5+5,使用到 3 枚硬币。

对于样例数据 2,最佳方案是 12=11+112=11 + 1,使用到 2 枚硬币。

数据规模与约定

对于 100%100\% 的数据,保证 n106n\leq 10^6