Sun. Jul 3rd, 2022

# Cops and the Thief Devu Codechef Solution

#### Bydivya katoch

Nov 7, 2021

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: Mx 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

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

```0
18
9
```

### Explanation

Example 1 : Cops in house 12 can cover houses 1 to 68, and cops in house 52 can cover the rest of the houses. So, there is no safe house.

Example 2 : Cops in house 21 can cover houses 1 to 41, and cops in house 75 can cover houses 55 to 95, leaving houses numbered 42 to 54, and 96 to 100 safe. So, in total 18 houses are safe.

## Cops and the Thief Devu – CodeChef Solution in JAVA

```import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
try {

int t = sc.nextInt();//... test cases
while(t-- > 0)
{
int M = sc.nextInt(); // ...M hosues of cops out of 100
int x = sc.nextInt(); //...maximum speed of cops is [x houses per min]
int y = sc.nextInt();  //....y minutes to serch..(at max)
int arr[] = new int[M];
for (int i=0;i<M ;i++)
{arr[i]= sc.nextInt();}  // ..array insertion

int count=0;
int till = x*y; //..
for(int i=1;i<=100 ;i++)
{
boolean safe = true;
for(int j=0; j<M; j++)
{  int min = Math.max(1,arr[j]-till);
int max = Math.min(100,arr[j]+till);
if(i>=min && i<=max)
{ safe = false;  }

}
if(safe){count++;}
}
System.out.println(count);

}

} catch(Exception e) { return;
}

}
}
```

## Cops and the Thief Devu – CodeChef Solution in CPP

```#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int M,x,y;
int a[101]={0};
cin>>M>>x>>y;
int b[101];
for(int i=0;i<M;i++){
cin>>b[i];
}
int d=x*y;
int count=0;
for(int i=1;i<101;i++){
int flag=1;
for(int j=0;j<M;j++){
if((i>=b[j]-d)&&(i<=b[j]+d)) flag=0;
}
if(flag==1) count++;
}
cout<<count<<endl;

}
return 0;
}

```

## Cops and the Thief Devu-CodeChef Solution in Python

```for i in range(int(input())):
m,x,y=map(int,input().split())
l=list(map(int,input().split()))
k=x*y
a=[i for i in range(100)]
p=[]
for i in l:
if i<=k:
p.extend(a[:i+k])
else:
p.extend(a[i-k-1:i+k])
p=list(set(p))
print(100-len(p))```

Disclaimer: The above Problem (Cops and the Thief Devu ) is generated by CodeChef but the solution is provided by Codeworld19.This tutorial is only for Educational and Learning purpose.