| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 서브태스크 참고 (추가 시간 없음) | 1024 MB | 14 | 7 | 7 | 70.000% |
Glide Typing task in Crowdsource app uses a new Google keyboard to type a word by sliding a finger across keys without lifting the finger, as shown in the animation below.
To make the Glide Typing task more challenging, instead of a normal keyboard, we have a special linear keyboard $\mathbf{K}$ that has all the keys in one row.
Imagine that you want to type a word $\mathbf{S}$ that is $\mathbf{N}$ characters long. The linear keyboard $\mathbf{K}$ has $\mathbf{M}$ keys. It is guaranteed that the keys cover all characters in $\mathbf{S}$. However, some of the keys may be duplicates. In other words, for each character in $\mathbf{S},ドル there is one or more keys in $\mathbf{K}$ mapped to the character. Note that, all characters and keys are represented as integers.
You may start with your finger on any key. It takes 1ドル$ second to move your finger from a key to an adjacent key. Due to Glide Typing, there is no pressing a key. If the finger is currently at the key $i$ which has character $\mathbf{K_i},ドル and we want to type the character $\mathbf{K_j}$ at index $j,ドル we will glide the finger from the key $i$ to the key $j,ドル which takes $\lvert j-i \rvert$ seconds. If your finger is at key $x,ドル you can type character $\mathbf{K_x}$ any number of times instantly. You need to type string $\mathbf{S}$ character by character. Formally, you need to type $\mathbf{S_i}$ before $\mathbf{S_{i+1}}$ for each $ 1 \le i \le \mathbf{N}-1 $.
For example, suppose the word $\mathbf{S}$ has characters: 1, 2, 2, 3, 4. You can start by keeping your finger on key with character 1 on the keyboard which is at index $i$. Then you glide your finger to key which has character 2 which is at index $j$. It would take $\lvert j-i \rvert$ seconds. In order to type character 2 two times in string $\mathbf{S},ドル you can do that in no additional time as $\lvert j-j \rvert = 0$ seconds. Then you can continue to glide your finger to type the other characters in the word $\mathbf{S}$ sequentially.
Can you calculate the minimal time needed to type the word?
The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.
The first line of each test case contains one integer $\mathbf{N}$: the length of the word $\mathbf{S}$.
The second line of each test case contains $\mathbf{N}$ integers: each $\mathbf{S_i}$ is the character at the $i$-th index.
The third line of each test case contains one integer $\mathbf{M}$: the length of the keyboard $\mathbf{K}$.
The fourth line of each test case contains $\mathbf{M}$ integers: each $\mathbf{K_i}$ is the character at the $i$-th key.
For each test case, output one line containing the minimal time needed to type the word. Case #$x$: $y$, where $x$ is the test case number (starting from 1) and $y$ is the minimal time needed to type $\mathbf{S}$ on the keyboard $\mathbf{K}$.
시간 제한: 20 초
시간 제한: 20 초
시간 제한: 40 초
2 5 1 2 3 2 1 3 1 2 3 3 1 1 1 2 2 1
Case #1: 4 Case #2: 0
In Sample Case #1, we can take the following steps to type string $\mathbf{S}$ in minimum time.
1. We have now typed the first character of the string $\mathbf{S}$.2 of the string $\mathbf{S},ドル glide your finger to key $\mathbf{K_2}$. it takes $\lvert 2 - 1 \rvert = 1$ additional second to glide the finger from index 1ドル$ to index 2ドル$.3 of the string $\mathbf{S},ドル glide your finger to key $\mathbf{K_3}$. it takes $\lvert 3 - 2 \rvert = 1$ additional second to glide the finger from index 2ドル$ to index 3ドル$.2 of the string $\mathbf{S},ドル glide your finger to key $\mathbf{K_2}$. it takes $\lvert 2 - 3 \rvert = 1$ additional second to glide the finger from index 3ドル$ to index 2ドル$.1 of the string $\mathbf{S},ドル glide your finger to key $\mathbf{K_1}$. it takes $\lvert 1 - 2 \rvert = 1$ additional second to glide the finger from index 2ドル$ to index 1ドル$.In Sample Case #2, we can take the following steps to type string $\mathbf{S}$ in minimum time.
1. We have now typed the first character of the string $\mathbf{S}$.1 any number of times, without any additional time. Hence, we can type the second and third characters of the string $\mathbf{S}$.2 4 2 1 4 1 8 4 1 5 2 1 3 5 4 3 1 2 3 8 2 3 5 1 4 6 7 2
Case #1: 4 Case #2: 4
In Additional Sample Case #1, we can take the following steps to type string $\mathbf{S}$ in minimum time.
2. We have now typed the first character of the string $\mathbf{S}$.1 of the string $\mathbf{S},ドル glide your finger to key $\mathbf{K_2}$. it takes $\lvert 2 - 4 \rvert = 2$ additional seconds to glide the finger from index 4ドル$ to index 2ドル$.4 of the string $\mathbf{S},ドル glide your finger to key $\mathbf{K_1}$. it takes $\lvert 1 - 2 \rvert = 1$ additional second to glide the finger from index 2ドル$ to index 1ドル$.1 of the string $\mathbf{S},ドル glide your finger to key $\mathbf{K_2}$. it takes $\lvert 2 - 1 \rvert = 1$ additional second to glide the finger from index 1ドル$ to index 2ドル$.In Additional Sample Case #2, we can take the following steps to type string $\mathbf{S}$ in minimum time.
1. We have now typed the first character of the string $\mathbf{S}$.2 of the string $\mathbf{S},ドル glide your finger to key $\mathbf{K_1}$. it takes $\lvert 1 - 4 \rvert = 3$ additional seconds to glide the finger from index 4ドル$ to index 1ドル$.3 of the string $\mathbf{S},ドル glide your finger to key $\mathbf{K_2}$. it takes $\lvert 2 - 1 \rvert = 1$ additional second to glide the finger from index 1ドル$ to index 2ドル$.Contest > Google > Kick Start > Google Kick Start 2022 > Round D C번