Cops and the Thief Devu Codechef Solution

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

Sample Input 1 

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

Sample Output 1 

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.

Leave a Reply

Your email address will not be published. Required fields are marked *