Attraction

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

You are venturing deep in a run-down factory in search for the rare Zusniesium metal, and at last you have found some. Specifically, there are N pieces of Zusniesium lined up equidistantly on a conveyor belt, on positions we can label from 1 to N. There are also A fixed and deactivated attractors located at distinct positions underneath the conveyor belt. Once activated, any piece of Zusniesium will be attracted to the closest attractor, provided that the closest attractor is unique. Luckily, you have brought B removable attractors of your own which you may attach to distinct positions where there is no pre-existing attractor. After activating all A+B attractors simultaneously, any piece of Zusniesium attracted to one of your own attractors are yours to keep. Please write a program to find the maximum number of Zusniesium pieces you can take home, provided that you are allowed to attach at most B of your own attractors before activating all the attractors. To ensure the integrity of your solution, there may be multiple test cases.

Input Specification

The first line contains an integer T, the number of test cases. The next 2T lines will describe the test cases.

The first line of each test case contains 3 integers N, A, and B, as described in the statement.

The second line of each test case contains A distinct integers P_i (1 \le i \le A), the positions of the fixed attractors.

Output Specification

For each test case output one integer on its own line, the maximum number of Zusniesium pieces you can take home provided that you are allowed to attach at most B of your own attractors before activating all the attractors.

Constraints

For this problem, you will NOT be required to pass the sample case in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le T \le 10^5

1 \le N \le 10^9

1 \le A, B \le 2 \times 10^5

2 \le A + B \le N

1 \le P_i \le N

In each test case, all P_i are pairwise distinct.

The sum of A over all test cases will not exceed 2 \times 10^5.

The sum of B over all test cases will not exceed 2 \times 10^5.

Subtask 1 [15%]

B = 1

Subtask 2 [85%]

No further constraints.

Sample Input

3
11 2 3
2 10
10 2 5
1 10
6 4 2
5 1 4 3

Sample Output

7
8
2

Explanation

For the first test case, one possible solution is to place your own attractors on positions 3, 9, and 11. This will attract the Zusniesium pieces located at positions 3, 4, 5, 7, 8, 9, 11. Note that the Zusniesium piece at position 6 is not attracted to any attractor, since there is no unique closest attractor. This scenario is illustrated in the diagram above, where circles in red rectangles represent Zusniesium pieces attracted to the fixed attractors, while circles in blue rectangles represent Zusniesium pieces attracted to your own attractors.

For the second test case, one possible solution is to place 4 of your own attractors on positions 2, 5, 8, and 9. These will attract all the Zusniesium metal from position 2 to position 9, leaving you with 8 Zusniesium pieces in total. Note that you do not have to use all of your attractors.

For the last test case, the best you can do is place your 2 attractors on the only 2 unoccupied positions, leaving you with 2 Zusniesium pieces in total.


Comments

There are no comments at the moment.