NOIP 提高组初赛 · NOIP 2009 提高组初赛试题 第 22 题

某个国家的钱币面值有 $1, 7, 7^2, 7^3$ 共计四种，如果要用现金付清 $10015$ 元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通_______张钱币。

使用1,7,49,343四种面值支付10015元，允许找零。将10015转化为七进制表示，每位用平衡策略选择支付或找零使总张数最小，答案为35。

容易直接做进制转换求各位数字和（得到37张），但需要考虑"允许找零"意味着可以进位优化。需要正确理解最大面值343对应的进制位限制。

解题思路

方法：七进制与最优支付策略

四种面值：1, 7, 49, 343（即7^0, 7^1, 7^2, 7^3）

将10015转换为七进制：

• 10015 / 7 = 1430 余 5
• 1430 / 7 = 204 余 2
• 204 / 7 = 29 余 1
• 29 / 7 = 4 余 1
• 4 / 7 = 0 余 4

所以10015的七进制表示为：4,1,1,2,5（从高到低） 即 4x7^4 + 1x7^3 + 1x7^2 + 2x7 + 5 = 9604 + 343 + 49 + 14 + 5 = 10015

注意：最大面值为343（7^3），更高位（7^4=2401）没有对应面值，需用343的组合表示。

直接支付

• 万位4需要 4x7 张343 = 28张
• 千位1需要 1张343
• 百位1需要 1张49
• 十位2需要 2张7
• 个位5需要 5张1

总张数 = 28 + 1 + 1 + 2 + 5 = 37张

允许找零优化

允许找零时，对于每位数字d可以选择：

• 直接支付d张（成本d）
• 支付1张更高面值，找零(7-d)张（成本1+7-d=8-d）

对于每位，选择成本较小的方案，并考虑进位影响。

经优化后，总张数可从37张降至35张。

更一般的思路

该问题等价于：找一组整数xi,yi>=0，使得 sum(xi * 7^i) - sum(yi * 7^i) = 10015，且最小化 sum(xi + yi)。这是一个允许找零的整数线性组合优化问题。

由于只有4种面值，高位需要转化为低位面值的组合，最终通过贪心从低位到高位逐位决策得到最优解为35张。