Informatica Online Judge

  다이얼 비밀번호 [1012 / 03F4]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 193   Total Tried : 250


The Champion of this Problem (C++) : gs15084 - ms / 491byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

다음과 같이 4자리 다이얼 자물쇠가 있다. 일반 다이얼 자물쇠와는 달리 이 자물쇠는 조금 독특한 면이 있다. "1123"에서 1의 자리를 1 위로 돌리면 "1124"가 된다. 여기까지는 일반적인 다이얼 자물쇠와 같다.

하지만 "1119"에서 1의 자리를 1위로 올리면 일반적인 자물쇠는 "1110"이 된다. 하지만 이 자물쇠는 "1120"이 되어, 실제 수가 증가하는 것과 같은 형식으로 동작하도록 설계되어 있다.

내리는 것도 마찬가지 이다. "1120"에서 1의 자리를 1내리면 "1129"가 되는 것이 아니라 "1119"가 된다.

"9999"에서 1의 자리를 1 올리면 "0000"이 되고, "1000"에서 10의 자리를 1번 내리면 "0990"이 된다.



이 자물쇠의 비밀번호 4자리가 "7654"라고 하고 현재 번호가 "7645"라고 하면 10의 자리 4를 5로 1올리고, 1의자리 5를 4로 1내리면 2번의 조작으로 비밀번호를 맞출 수 있다.

그런데 이 자물쇠는 특별한 보안장치가 있다. 어떤 임의의 숫자 조합으로는 절대 맞출 수 없다.

예를 들어 현재 번호가 "7779"이고 비밀번호가 "7777"이라면, 1의 자리 9를 2번 내려서 "7777"을 만들 수 있다.

하지만 보안 기능이 있는 자물쇠에는 절대로 맞출 수 없는 조합이 주어진다. 만이 이 상태에서 "7778"이 절대로 맞출 수 없는 번호라면 "7779" - "7778" - "7777"로는 갈 수 없다.

따라서 이 때는 "7779" - "8779" - "8778" - "8777" - "7777" 등의 다른 방법으로 맞춰야 한다.

현재번호와 비밀번호, 그리고 절대로 맞출 수 없는 보안번호가 주어질 때, 현재번호로 부터 비밀번호를 만들기 위한 최소의 조작횟수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 현재번호와 비밀번호가 공백으로 구분되어 입력된다.
두 번째 줄에 보안번호의 수 n이 입력된다.
다음 줄부터 n줄에 걸쳐서 보안번호가 한 줄에 하나씩 입력된다.

[입력값의 정의역]
0 <= n <= 1,000
항상 4자리수로 구성되며 각 자릿수의 값은 0이상 9이하의 숫자이다.

[Sub-task Info]
#1 : n = 0 (25%)
#2 : n = 1 (25%)
#3, #4 : 문제의 주어진 조건과 같다. (50%)

Output

비밀번호를 맞추기 위한 최소 조작횟수를 출력한다.
단, 비밀번호를 절대로 맞출 수 없다면 "-1"을 출력한다.

IO Example

입력1
7779 7777
0

출력1
2

*보안번호가 없으므로 2회의 조작으로 가능하다.

입력2
7779 7777
1
7778

출력2
4

* 설명 : 위 예시와 같이 4회의 조작으로 비밀번호를 맞출 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]