log in
Active Users
Feedback
About and Contact
© 2020 DOUBTCOOL
Cops and the Thief Devu
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.
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.
7 regular answers available
C++ program solution
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int t;
cin>>t;
while(t--) {
int m,x,y,h=0;
cin>>m>>x>>y;
int a[m];
for(int i=0;i<m;i++) {
cin>>a[i];
}
sort(a,a+m);
int s = x*y;
for(int i=0;i<m;i++) {
if(i==0) {
if(a[i]-s > 1) {
h += a[i]-s-1;
}
}
if(i==m-1) {
if(a[i]+s < 100) {
h += 100 - (a[i]+s);
}
}
else {
if(a[i]+s < (a[i+1]-s)) {
h += (a[i+1]-s) - (a[i]+s+1);
}
}
}
cout<<h<<endl;
}
// your code goes here
return 0;
}
python program :-
Explanation :
m = Number of house is the straight row.
x = speed of searching the houses per minute in a straight line
y = maximum minutes they can search the house
NOTE * the cops can search the houses the forward as well as backward direction
maximum houses per cops-house can search is x*y.
Now the inputs
first line is number of testcases.
second line is the m,x,y.
third line is the house numbers of m houses.
**for example
1
4 6 7
12 34 67 89
now the cops at first house will search forward and backward x*y number of house i.e HOUSE12 will 12 to x*y in forward and 12 to
x*y in backward. hence house in these ranges are not safe.
and these non safe house numbers are noted i,e stored in array.
similarly ,
this algorithm will applied to all the cop house.
at the final non-safe house number are made into a array and count the length of the array.
so the number of safe house are 100-length(The non-safe distinct array)
c=[]
for t in range(int(input())):
m,x,y=map(int, input().split())
h=list(map(int, input().split()))
for i in range(len(h)):
a=h[i]+x*y
if a>100:
a=100
b=h[i]-x*y
if b<1:
b=1
for k in range(b,a+1):
c.append(k)
c=set(c)
print(100-len(c))
here 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.
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.
c=[]
for t in range(int(input())):
m,x,y=map(int,
input().split())
h=list(map(int,
input().split()))
for i in range(len(h)):
a=h[i]+x*y
if a>100:
a=100
b=h[i]-x*y
if b<1:
b=1
for k in range(b,a+1):
c.append(k)
c=set(c)
print(100-len(c))