We have a Number N and Cost C,(range N<10^18 ,C<100) Now we have to spend maximum of C rupees to convert the number into another.
The rules of conversion of a number to another are as follows:
1)A number can be converted into other number with same number of digits and no leading zeros. 2)The cost of converting a number into other is the sum of absolute difference of corresponding digits. For example, Cost to convert 235 to 331 is 5 (since the absolute difference in corresponding digits is |3−2|+|3−3|+|1−5| , which is |1|+0+|−4|=5. Now we need to find how many numbers that are multiple of 3, which can be made within the maximum budget(C rupees).
My approach: i tried first to use divisibility rule of 3 and find sum of digits of N now if cost was just sum of difference of digits then we could simply do is make the sum a multiple of 3 like 2+3+5 = 10 cost is 2 we can make it 12 which can be achieved by increasing any number 2 , 3 or 5 by 2 435,255, 237 is this correct? also how to go about solving it in this case when c is absolute sum
Let cost(a,b) denote the cost of transforming a into b and define
N(a,c) = # { b | cost(a,b) = c }
i.e., N(a,c) is the number of numbers whose cost from a is exactly c.
Let's futher suppose _a_is divisible by 3. Then the number we are interested in is:
answer = N(a,0) + N(a,3) + N(a,6) + N(a,9) + ... + N(a,99)
If a was 1 mod 3 we would want the sum N(a,2) + N(a,5) + ... + N(a,98).
To compute N(a,c), for each digit d in a, construct a polynomial P(d) where the coefficient of x^k is the number of digits in [0..9] which are exactly k away from d. These coefficients will always be 0, 1 or 2.
For example, for a = 3496 the polynomials are:
d 1 x x^2 x^3 x^4 x^5 x^6 x^7 x^8 x^9
-- --- --- --- --- --- --- --- --- --- ---
3 1 2 2 1 1 1 1 0 0 0
4 1 2 2 2 2 1 0 0 0 0
9 1 1 1 1 1 1 1 1 1 1
6 1 2 2 2 1 1 1 0 0 0
N.B.: The coefficient of x^3 for the digit 3 is 1 and not 2 because leading zeros are not allowed.
Now multiply the polynomials together and N(a,c) is coefficient of x^c in the resulting product.