Cops and the Thief Devu Solution

Problem

There are 100 houses located on a straight line. The first house is numbered 1 and the last one is numbered 100. Some M houses out of these 100 are occupied by cops.

Thief Devu has just stolen PeePee's bag and is looking for a house to hide in.

PeePee uses fast 4G Internet and sends the message to all the cops that a thief named Devu has just stolen her bag and ran into some house.

Devu knows that the cops run at a maximum speed of x houses per minute in a straight line and they will search for a maximum of y minutes. Devu wants to know how many houses are safe for him to escape from the cops. Help him in getting this information.

Input

First line contains T, the number of test cases to follow.

First line of each test case contains 3 space separated integers: M, x and y.

For each test case, the second line contains M space separated integers which represent the house numbers where the cops are residing.

Output

For each test case, output a single line containing the number of houses which are safe to hide from cops.

Constraints

• 1 ≤ T ≤ 104
• 1 ≤ x, y, M ≤ 10

Sample 1:

Input

Output

3
4 7 8
12 52 56 8
2 10 2
21 75
2 5 8
10 51

0
18
9

Explanation:

Test case $1$: Based on the speed, each cop can cover $56$ houses on each side. These houses are:

• Cop in house $12$ can cover houses $1$ to $11$ if he travels left and houses $13$ to $68$ if he travels right. Thus, this cop can cover houses numbered $1$ to $68$.
• Cop in house $52$ can cover houses $1$ to $51$ if he travels left and houses $53$ to $100$ if he travels right. Thus, this cop can cover houses numbered $1$ to $100$.
• Cop in house $56$ can cover houses $1$ to $55$ if he travels left and houses $57$ to $100$ if he travels right. Thus, this cop can cover houses numbered $1$ to $100$.
• Cop in house $8$ can cover houses $1$ to $7$ if he travels left and houses $9$ to $64$ if he travels right. Thus, this cop can cover houses numbered $1$ to $64$.

Thus, there is no house which is not covered by any of the cops.

Test case $2$: Based on the speed, each cop can cover $20$ houses on each side. These houses are:

• Cop in house $21$ can cover houses $1$ to $20$ if he travels left and houses $22$ to $41$ if he travels right. Thus, this cop can cover houses numbered $1$ to $41$.
• Cop in house $75$ can cover houses $55$ to $74$ if he travels left and houses $76$ to $95$ if he travels right. Thus, this cop can cover houses numbered $55$ to $95$.

Thus, the safe houses are house number $42$ to $54$ and $96$ to $100$. There are $18$ safe houses.

Program :

 #include <stdio.h>

int main(void) {

// your code goes here

int t;

scanf("%d",&t);

while(t--)

{

    int m,x,y,i;

    scanf("%d %d %d",&m,&x,&y);

    int a[m];

    for(i=0;i<m;i++)

    {

        scanf("%d",&a[i]);

    }

    int count=0,j,k,p,q,r;

    for(j=1;j<=100;j++)

    {

        r=0;

        for(k=0;k<m;k++)

        {

            q=a[k]-x*y;

            p=a[k]+x*y;

            if(j>=q && j<=p)

            {

               r=1;

            }

        }

        if(r==0)

        {

            ++count;

        }

    }

    printf("%d\n", count);

}

return 0;

}