-2

数値 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 の桁の合計を見つけようとしました。コストが単に桁の差の合計である場合、単純に合計を 2+3+5 = 10 のように 3 の倍数にすることができます。コストは 2 です。12 にすることができます。これは、任意の数 2 、3 または 5 を 2 435,255, 237 で増やすことによって達成できます。これは正しいですか? また、cが絶対和の場合、この場合にそれを解決する方法

4

1 に答える 1

0

cost( a ,b)は、aをbに変換するコストを表し、次のように定義します。

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

つまり、N(a,c)は、a からのコストが正確にcである数値の数です。

さらに、_a_が 3 で割り切れると仮定しましょう。その場合、関心のある数値は次のとおりです。

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

aが 1 mod 3の場合、合計N(a,2) + N(a,5) + ... + N(a,98) が必要になります。

N(a,c)を計算するには、 aの各桁dに対して、多項式P(d)を作成します。ここで、 x^kの係数は[0..9] の桁数で、 dからちょうどk 離れています。これらの係数は常に 0、1、または 2 です。

たとえば、a = 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のx^3の係数は2 ではなく 1 です。これは、先行ゼロが許可されていないためです。

多項式を掛け合わせると、N(a,c)は 結果の積のx^cの係数になります。

于 2015-01-24T20:30:23.050 に答える