TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

92.6% (63/68)

Submission's AC Ratio

32.0% (96/300)

Description

小智買了一個神奇的數字密碼鎖,這個數字密碼鎖總共有 n 個介於 1 到 9 的正整數,每次調整密碼鎖上的數字時,必須一次調整其中連續的 k 個數字,並且只能將這 k 個數字分別調大一個數字。例如,若原來的數字是 5,則調整後變成 6,但若原來的數字是 9,則調整後的數字將變成 1。
因此,若 n = 5,且原來的這五個數字分別是 1 2 3 4 9。當 k = 2 時,共有四種調整的方法,而調整後的結果共有四種可能,分別是 2 3 3 4 9、1 3 4 4 9、1 2 4 5 9、和 1 2 3 5 1。
給定 n 和 k 的值,已知目前數字密碼鎖上的 n 個數字 $a_1 a_2 ... a_n$,及解開密碼鎖所需要的 n 個數字 $b_1 b_2 ... b_n$,請計算小智最少需要調整幾次密碼鎖,才能將數字密碼鎖成功解開(亦即,由 $a_1 a_2 ... a_n$ 變成 $b_1 b_2 ... b_n$)。

Input Format

輸入的第一行有二個以一個空白符號隔開的正整數 n 和 k,代表數字密碼鎖上有幾位數,以及每次可以調整幾位數;第二行有 n 個以空白符號相間隔,並且介於 1 到 9 的正整數,代表數字密碼鎖上原有的 n 個數字;第三行也有 n 個以空白符號相間隔,並且介於 1 到 9 的正整數,代表解開數字密碼鎖所需要的 n 個數字。注意,數字密碼鎖的起始設定是鎖定的狀態(至少需要一次以上的調整,才能解開數字密碼鎖)。

Output Format

輸出一整數,即最少需要進行幾次調整才能解開密碼鎖。若密碼鎖不可能被解開,則輸出 0。

Sample Input

Sample Input #1:
9 2
1 2 3 4 5 6 7 8 9
1 2 3 4 6 7 7 9 1

Sample Input #2:
9 2
1 2 3 4 5 6 7 8 9
1 2 3 4 6 7 7 9 9

Sample Output

Sample Output #1:
2

Sample Output #2:
0

Hints

Problem Source

2017北市賽(prob 3)

Subtasks

No. Testdata Range Constraints Score
1 0~6 $n=k=2$ 10
2 7~16 $2 < n \leq 5, k=2$ 17
3 17~27 $5 < n \leq 100, k=2$ 22
4 28~59 $10 < N \leq 10000, k < 100$ 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 500 524288 262144 1
1 500 524288 262144 1
2 500 524288 262144 1
3 500 524288 262144 1
4 500 524288 262144 1
5 500 524288 262144 1
6 500 524288 262144 1
7 500 524288 262144 2
8 500 524288 262144 2
9 500 524288 262144 2
10 500 524288 262144 2
11 500 524288 262144 2
12 500 524288 262144 2
13 500 524288 262144 2
14 500 524288 262144 2
15 500 524288 262144 2
16 500 524288 262144 2
17 500 524288 262144 3
18 500 524288 262144 3
19 500 524288 262144 3
20 500 524288 262144 3
21 500 524288 262144 3
22 500 524288 262144 3
23 500 524288 262144 3
24 500 524288 262144 3
25 500 524288 262144 3
26 500 524288 262144 3
27 500 524288 262144 3
28 500 524288 262144 4
29 500 524288 262144 4
30 500 524288 262144 4
31 500 524288 262144 4
32 500 524288 262144 4
33 500 524288 262144 4
34 500 524288 262144 4
35 500 524288 262144 4
36 500 524288 262144 4
37 500 524288 262144 4
38 500 524288 262144 4
39 500 524288 262144 4
40 500 524288 262144 4
41 500 524288 262144 4
42 500 524288 262144 4
43 500 524288 262144 4
44 500 524288 262144 4
45 500 524288 262144 4
46 500 524288 262144 4
47 500 524288 262144 4
48 500 524288 262144 4
49 500 524288 262144 4
50 500 524288 262144 4
51 500 524288 262144 4
52 500 524288 262144 4
53 500 524288 262144 4
54 500 524288 262144 4
55 500 524288 262144 4
56 500 524288 262144 4
57 500 524288 262144 4
58 500 524288 262144 4
59 500 524288 262144 4