15届noip初赛问题求解2

2、某个国家的钱币面值有1，7，7^2，73共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通______张钱币。 首先先看10015分别包含多少个上述面值的钱币，那么我们要把10015化成10015=a7^{3+b72+c70+d7^0 这种形式 看起来是不是很熟悉？ 没错，这就是7进制转10进制的步骤。 明显，先把10015转换成7进制41125，那么a,b,c,d就可得知。 10015（10）=41125（7）=474+173+17}2+27+5 =（47+1）7^{3+172+27+5 =2973+17}2+27+5 可以得出，如果不能找零，那么需要37张去付款。 那么可以找零的话，我们可以尝试多加一张大的，并加一些小的用作找零。 首先，对于a7^(i+1),b*7^i a,b∈N 多拿一张7^(i+1)面值的纸币，那么多出 7^{(i+1)-b7^i =7i7-b7i =(7-b)7}i 显然，需要用7-b张较小的找零。 那么总共需要1+7-b张 对比原来的b张 我们要比原来更少的张数 那么 1+7-b<b (注意这里没有加上a来算，结果一样) 8<2b b>4 可以得出只要较小的张数b>4，那么加一张较大的并上找零需要的张数一定比原来的较小的张数小。 另外，根据1+7-b可以看出，b越大，新的张数越小。 最后，我们可以轻而易举的得出，找出7进制中大于4的数，不算第5,4位（没有比他更大面值的纸币了），用一张较大的加找零的替换。 若有多个大于4的，从小往大替换。 对于本题 把第5位用较大的替换，那么替换后有1+7-5=3张 加上前面的，最少需要29+1+2+3=35张。