TopCoder

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

User's AC Ratio

97.1% (34/35)

Submission's AC Ratio

46.7% (57/122)

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 個數字。注意,數字密碼鎖的起始設定是鎖定的狀態(至少需要一次以上的調整,才能解開數字密碼鎖)。

子任務(測資) 額外限制 分數
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

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

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