만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

수 만들기

시간 제한1.5초메모리 제한1024 MB

요약
A를 B로 바꾸는 최소 비용을 구합니다. 한 자리 숫자를 바꾸면 차이만큼, 정수 y를 더하면 |y|만큼 비용이 듭니다.
난이도

보통10점 중 6점

유형
최단 경로, 동적 계획법, 구현
정답자
아직 제출이 없습니다

문제

두 양의 정수 A,BA, B가 주어집니다.

AA에 다음 두 가지 연산을 순서와 횟수에 상관없이 원하는 만큼 반복할 수 있습니다.

  1. AA의 10진법 표현을 dk−1⋯d0d_{k-1} \cdots d_0이라고 합시다. 즉, A=∑i=0k−1di⋅10iA = \sum_{i=0}^{k-1} d_i \cdot 10^i이고, did_i는 0≤di≤90 \le d_i \le 9를 만족하는 정수이며, dk−1≠0d_{k-1} \ne 0입니다. 임의의 정수 ii (0≤i<k0 \le i < k)와 xx (0≤x≤90 \le x \le 9)를 골라 did_i를 xx로 바꿉니다. 단, i=k−1i = k-1이라면 0<x≤90 < x \le 9를 만족해야 합니다. 이 연산의 비용은 ∣x−di∣|x - d_i|입니다.
  2. y>−Ay > -A인 임의의 정수 yy를 골라 AA에 더합니다. 이 연산의 비용은 ∣y∣|y|입니다.

예를 들어 수 2024에서 i=1i=1, x=7x=7을 골라 1번 연산을 수행하면 2074가 되며, 이 연산의 비용은 ∣7−2∣=5|7-2| = 5입니다.

그러나 i=3i=3, x=0x=0을 골라 0024를 만들거나, i=4i=4, x=1x=1을 골라 12024를 만드는 것은 조건을 만족하지 않으므로 불가능합니다.

또한 수 926에 y=−926y=-926을 골라 2번 연산을 수행하여 0으로 만드는 것도 조건을 만족하지 않으므로 불가능합니다.

AA를 BB로 만드는 데 드는 비용 합의 최솟값은 얼마일까요?

입력

첫 번째 줄에 공백으로 구분된 두 양의 정수 A,BA, B (1≤A,B<5 000 0001 \le A, B < 5\,000\,000)가 주어집니다.

출력

AA를 BB로 만드는 데 드는 비용 합의 최솟값을 출력합니다.

예제2

  1. 예제 1

    입력
    1273 29856
    
    예상 출력
    33
    
  2. 예제 2

    입력
    2024926 2024926
    
    예상 출력
    0