Номер Мощность, кратный 3

Question

У нас есть номер N и стоимость C, (диапазон N < 10^18, C < 100) Теперь мы должны провести максимум C рупий, чтобы преобразовать число в другое.

Правила преобразования ряда к другому следующим образом:

1) число может быть преобразовано в другое число с таким же количеством цифр и без ведущих нулей. 2) Стоимость преобразования числа в другое представляет собой сумму абсолютной разницы соответствующих цифр. Например, стоимость преобразования 235 на 331 равна 5 (поскольку абсолютная разница в соответствующих цифрах равна | 3-2 | + | 3-3 | + | 1-5 |, которая равна | 1 | +0+ | -4 | . = 5 Теперь нам нужно найти, как много чисел, которые кратны 3, которые могут быть сделаны в пределах максимального бюджета (C рупий)

Мой подход:. я пытался первым использовать правило делимости из 3 и найти сумма цифр N теперь, если бы цена была просто суммой разницы цифр, мы могли бы просто сделать сумму, кратную 3 , как 2 + 3 + 5 = 10 стоимость 2 мы можем сделать это 12, что может быть достигается путем увеличения любого числа 2, 3 или 5 на 2 435,255, 237, это правильно? также как решить его в этом случае, когда c is ab растворенное вещество сумма

Answer 1

Пусть стоимости (а, б) обозначает стоимость преобразования в б и определить

N(a,c) = # { b | cost(a,b) = c } 

т.е. N (а, с) этим числом номера, стоимость которых от a - это точно c.

Давайте futher предположим _a_is делится на 3. Тогда число мы заинтересованы в том:

answer = N(a,0) + N(a,3) + N(a,6) + N(a,9) + ... + N(a,99) 

Если был 1 мод 3 мы хотели бы, чтобы сумма N (а, 2) + N (a, 5) + ... + N (a, 98).

Для вычисления N (A, C), для каждой цифры г в , построить многочлен Р (г), где коэффициент х^к это число цифр в [0..9], которые равны k от d. Эти коэффициенты всегда будут 0, 1 или 2.

Например, для а = 3496 многочлены:

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 

Примечание: Коэффициент х^3 для цифры 3 1, а не 2, потому что ведущие нули не разрешены.

Теперь умножать многочлены вместе и Н (а, с) является коэффициент х^с в полученном продукте.