2228C2.md (1567B)
1 Source: https://codeforces.com/problemset/problem/2228/C2 2 3 C2. Cirno and Number (Hard Version) 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Led On by a Cow to Visit Zenkou Temple 22 23 — Neo-traditionalism of Japan 24 25 This is the hard version of the problem. The difference between the versions is that in this version, $1\le n\le 10$. You can hack only if you solved all versions of this problem. 26 27 You are given a non-negative integer $a$ and a non-empty, strictly increasing sequence of digits $d$ of length $n$, where $0 \le d_i \le 9$. 28 29 Find the minimum value of $|a - b|$ over all non-negative integers $b$ whose decimal representation contains only digits from $d$. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 34 35 The first line of each test case contains two integers $a$ and $n$ ($0\le a\le 10^{17}$, $1\le n\le 10$). 36 37 The second line contains $n$ integers $d_1,d_2,\ldots,d_n$. It is guaranteed that $0\le d_1 \lt d_2 \lt \ldots \lt d_n\le 9$. 38 39 Output 40 41 For each test case, output the minimum value of $|a - b|$. 42 43 Example 44 45 Input 46 47 ``` 48 4 49 50 0 1 51 52 0 53 54 11 2 55 56 1 2 57 58 222 3 59 60 3 4 5 61 62 3333 4 63 64 6 7 8 9 65 ``` 66 67 Output 68 69 ``` 70 0 71 72 0 73 74 111 75 76 2334 77 ``` 78 79 Note 80 81 In the first test case, $a=0$, $b=0$, and $|a - b|=0$. 82 83 In the second test case, $a=11$, $b=11$, and $|a - b|=0$. 84 85 In the third test case, $a=222$, $b=333$, and $|a - b|=111$. 86 87 In the fourth test case, $a=3333$, $b=999$, and $|a - b|=2334$.