WITTYBOY - THE WITTY BOY

no tags 

The television at the boy's home contains the channels from 1 to n inclusive. The father wanted to avoid his son to watch some channels in the Television. You are given k unique channels that are banned by the father. For example assume that the TV contains 25 channels and the father bans the channels 15, 17 and 18 and you are currently at channel 16. If you press the 'down' button in the remote,  you will move to channel 14 and if you press the 'up' button in the remote, you will move to channel 19. Also if you press up button from channel 25 you will move to channel 1 and if you press down button from channel 1 you will move to channel 25. There are 13 buttons in the remote as shown in the figure.


To move to a channel you can press the digits of the channel or you can use Up/Down/Previous buttons. The previous button will take you to the immediately previous channel you watched. (The previous button does not take effect until you have moved to some other channel after the first one.)

The remote control responds to delays. So you can take the button presses "1" and "9" either as a way to go to channel 1 and then to channel 9, or to channel 19 directly.

You are given the sequence of channels that the boy wanted to watch. Find the minimum number of remote button presses required by the boy. It's not necessary to watch the given channels consecutively, but it is necessary to watch them in the order specified. (In other words, the given sequence must be a subsequence of the optimal channel series the boy chooses to watch.)

To watch the first channel in the sequence, you must press the digits of the channel.


Input:

The first line consists of and integer t, the number of test cases. Each test case consists of 4 lines. The first line consists of 2 integers n and k, the number of channels in the remote and the number of channels blocked. The next line consists of k unique integers - the id of the blocked channels. The next line consists of an integer m the number of channels the boy wants to watch followed by a line with m integers - the channel id's of the channels that the boy wants to watch.

Output:

For each test case print the minimum number of remote button clicks required.

Input Constraints:

1 <= t <= 100

1 <= n <= 1000

0 <= k <= n-1

1 <= m <= 1000

ChannelToWatch[i] != ChannelToWatch[i-1]

ChannelToWatch[any] != BannedChannel[any]


Sample Input:

3

5 0

 

5

1 2 3 4 5

500 0

 

4

140 160 139 160

5 2

2 4

5

1 3 5 3 5

Sample Output:

Case #1: 5

Case #2: 9

Case #3: 5

 

Note: Suppose you are currently at channel 6 and press up button twice you will move to channel 8. Now if you click on previous button, you will move to channel 7 and not channel 6.

Explanation of Case #2:

The moves are "1", "4", "0", "down", "1", "6", "0", "previous", "previous"

 

Congrats and thanks to Mitch Schwartz for solving this problem first and for helping on setting test cases for this problem.


hide comments
Oleg: 2023-12-25 23:43:11

Nice one!
Clarifications for description:
1) First you have to go directly to first channel from required list.
2) You can't press digits of banned channel.
3) Some tricky cases! Don't give up!
4) N <= 1000... but probably about same complexity would work for N <1e9, K <= 1e5, M <= 1e3.

Last edit: 2023-12-26 23:28:55
[Rampage] Blue.Mary: 2017-09-24 10:57:30

Indeed, not as easy as it seems like.

Last edit: 2023-12-22 02:38:17
:D: 2015-04-27 22:36:54

Ok, this is a definition of "harder than it looks". Witch doesn't at all mean it's a bad problem :) Thanks Prakash and Mitch, great work.


Added by:cegprakash
Date:2013-02-24
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU