Thief and Police solution – There is an NN by MM grid. A thief is trying to escape from a policeman 2021

Thief and Police solution

Thief and Police solution

There is an NN by MM grid. A thief is trying to escape from a policeman. The thief is currently in cell (x,y)(x,y) in the grid, while the policeman is in cell (a,b)(a,b). Cells are numbered from 11 to NN, top to bottom, and 11 to MM, left to right. Both of them are at different cells initially. Thief and Police solution

Both of them take turns alternatively. First it is the thief’s turn, then the police’s, and so on. The thief needs to reach the cell (N,M)(N,M) to escape. In his turn, the thief can move either right, or down, from his current cell. In other words, if his current cell is (i,j)(i,j), then in one turn, he can either go to cell (i,j+1)(i,j+1) or the cell (i+1,j)(i+1,j).

He can’t stop, i.e., he needs to move during each of his turns. The policeman can move right, down, or (right ++ down) in one turn. In other words, in one turn, if his current cell is (i,j)(i,j), then he can go to the cell (i,j+1)(i,j+1), the cell (i+1,j)(i+1,j) or the cell (i+1,j+1)(i+1,j+1). It is not compulsory for the policeman to move every turn, i.e., he can choose to stay in his current cell in a particular turn of his. Neither of them are in cell (N,M)(N,M) at the start. Thief and Police solution

The policeman catches the thief if he’s in the same cell as the thief at any point of time, and he had reached that cell before the thief. If the thief reaches the cell (N,M)(N,M) before the policeman, then he shall escape. Find if the thief shall escape, or the policeman shall catch him, if both of them move optimally, and if both of them have perfect knowledge of the other person’s location at all times. Print YES if the thief shall escape, else print NO if the policeman shall catch him. Thief and Police solution

Thief and Police solution

Input: Thief and Police solution

  • The first line contains an integer TT, denoting the number of test cases.
  • The first line of each test case contains two space-separated integers NN and MM, denoting the number of rows and columns in the grid, respectively.
  • The second line of each test case contains two space-separated integers xx and yy, denoting the coordinates of the cell that the thief is in, initially.
  • The third line of each test case contains two space-separated integers aa and bb, denoting the coordinates of the cell that the policeman is in, initially.
  • Thief and Police solution Thief and Police solution

Output: Thief and Police solution

For each test case print YES if the thief shall escape, else print NO, in a separate line.

You may print each character of each string in uppercase or lowercase (for example, the strings “yEs”, “yes”, “Yes” and “YES” will all be treated as identical). Thief and Police solution

Constraints Thief and Police solution

  • 1T1051≤T≤105
  • 3N,M1053≤N,M≤105
  • 1x,aN1≤x,a≤N
  • 1y,bM1≤y,b≤M
  • Both of them are in different cells initially.
  • Neither of them are in cell (N,M)(N,M) initially.
  • The thief needs to move during every turn of his. The policeman can choose not to move.

Sample Input: Thief and Police solution

3
3 3
2 3
3 1
3 3
2 3
3 2
5 4
1 2
4 2

Sample Output:

YES
YES
NO

Explanation:

  • Sample Test 11: It’s the thief’s turn first. In his turn, he simply moves from his current cell, (2,3)(2,3) to the escape cell (3,3)(3,3) and escapes successfully.

  • Sample Test 22: Similar to the previous test case, the thief reaches the escape cell in his turn. The policeman too reaches the escape cell (3,3)(3,3) from his cell (3,2)(3,2) in his turn, but since the thief had already reached it in his turn, he manages to escape successfully.

  • Sample Test 33: The thief is initially at (1,2)(1,2), and needs to reach (5,4)(5,4). The police is initially at (4,2)(4,2). So initially, both of them are in the second column. The police waits at (4,2)(4,2) as long as the thief is in the second column. So he will either catch the thief at the cell (4,2)(4,2), or the thief moves to the third column at some point. And when he does so, the police moves to (4,3)(4,3) in his next turn, and waits there till the thief moves to the fourth column.

So, similar to the previous situation, the police will either catch the thief at the cell (4,3)(4,3), or the thief moves to the fourth column. And when the thief moves to the fourth column, the police moves to the cell (4,4)(4,4) and waits there, and will eventually catch the thief. Thus, the thief can’t escape.

Thief and Police solution

Program Code :

C++

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mpi map<ll,ll>
#define vl vector<ll>
#define vi vector<int>
#define pl pair<ll,ll>
#define pi pair<int,int>
#define forn(i,n) for(ll i=0;i<n;i++)
#define ff first
#define ss second
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define inf 1000000000000
#define MOD 1000000007
#define PI 3.14159265
ll binpow(ll a,ll b,ll m){
a%=m;
ll res=1;
while(b>0){
if(b&1)
res=res*a%m;
a=a*a%m;
b>>=1;
}
return res;
}
void solve(){
ll n,m,x,y,a,b;
cin>>n>>m>>x>>y>>a>>b;
ll k1=n-x+m-y;
ll c=n-a,d=m-b;
ll k2=c+d-min(c,d);
//cout<<k1<<" "<<k2;
if(k1<=k2){
cout<<"YES";
return;
}
cout<<"NO";

}

int main(){
ll t=1;
cin>>t;
while(t--){
solve();
cout<<endl;
}

return 0;
}

JAVA

//Some of the methods are copied from GeeksforGeeks Website 
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{ 
static Reader sc=new Reader();
// static FastReader sc=new FastReader(System.in);

public static void main (String[] args) throws java.lang.Exception
{
try{
/*
int n=sc.nextInt();
ArrayList<Integer> al=new ArrayList<>();
ArrayList<Long> al=new ArrayList<>();
Set<Integer> set=new HashSet<>();
Collections.sort(al,Collections.reverseOrder());

long n=sc.nextLong();
for(int i=0;i<n;i++) 
String s=sc.next();
*/
int t = sc.nextInt();
while(t-->0)
{ 
long n=sc.nextLong();long m=sc.nextLong();
long x=sc.nextLong();long y=sc.nextLong(); 
long a=sc.nextLong();long b=sc.nextLong();
long thief=n-x+m-y;
long pol=n-a+m-b-Math.min(n-a,m-b);
if(pol<thief)
out.println("NO");
else
out.println("YES");
}
out.flush();
out.close();
} 
catch(Exception e)
{}
}

/*
...SOLUTION ENDS HERE...........SOLUTION ENDS HERE...
*/

static void flag(boolean flag)
{
out.println(flag ? "YES" : "NO");
out.flush();
}

/* 
Map<Long,Long> map=new HashMap<>();
for(int i=0;i<n;i++)
{
if(!map.containsKey(a[i]))
map.put(a[i],1);
else
map.replace(a[i],map.get(a[i])+1);
}

Set<Map.Entry<Long,Long>> hmap=map.entrySet();
for(Map.Entry<Long,Long> data : hmap)
{

}

Iterator<Integer> it = set.iterator();
while(it.hasNext()) 
{ 
int x=it.next();
}
*/

static void print(int a[])
{
int n=a.length;
for(int i=0;i<n;i++)
{
out.print(a[i]+" ");
}
out.println();
out.flush();
}
static void print(long a[])
{
int n=a.length;
for(int i=0;i<n;i++)
{
out.print(a[i]+" ");
}
out.println();
out.flush();
} 
static void print_int(ArrayList<Integer> al)
{
int si=al.size();
for(int i=0;i<si;i++)
{
out.print(al.get(i)+" ");
}
out.println();
out.flush();
}
static void print_long(ArrayList<Long> al)
{
int si=al.size();
for(int i=0;i<si;i++)
{
out.print(al.get(i)+" ");
}
out.println();
out.flush();
}

static class Graph
{
int v;
ArrayList<Integer> list[];
Graph(int v)
{
this.v=v;
list=new ArrayList[v+1];
for(int i=1;i<=v;i++)
list[i]=new ArrayList<Integer>();
}
void addEdge(int a, int b)
{
this.list[a].add(b);
}
}
static void DFS(Graph g, boolean[] visited, int u)
{
visited[u]=true;
int v=0;
for(int i=0;i<g.list[u].size();i++)
{
v=g.list[u].get(i);
if(!visited[v])
DFS(g,visited,v);
}
} 

// static class Pair
// {
// int x,y;
// Pair(int x,int y)
// {
// this.x=x;
// this.y=y;
// }
// }

static long sum_array(int a[])
{
int n=a.length;
long sum=0;
for(int i=0;i<n;i++)
sum+=a[i];
return sum;
}
static long sum_array(long a[])
{
int n=a.length;
long sum=0;
for(int i=0;i<n;i++)
sum+=a[i];
return sum;
}

static void sort(int[] a) 
{
ArrayList<Integer> l=new ArrayList<>();
for (int i:a) l.add(i);
Collections.sort(l);
for (int i=0; i<a.length; i++) a[i]=l.get(i);
}
static void sort(long[] a) 
{
ArrayList<Long> l=new ArrayList<>();
for (long i:a) l.add(i);
Collections.sort(l);
for (int i=0; i<a.length; i++) a[i]=l.get(i);
}

static void reverse_array(int a[])
{
int n=a.length;
int i,t; 
for (i = 0; i < n / 2; i++) { 
t = a[i]; 
a[i] = a[n - i - 1]; 
a[n - i - 1] = t; 
} 
}
static void reverse_array(long a[])
{
int n=a.length;
int i; long t; 
for (i = 0; i < n / 2; i++) { 
t = a[i]; 
a[i] = a[n - i - 1]; 
a[n - i - 1] = t; 
} 
}

static long gcd(long a, long b) 
{ 
if (a == 0) 
return b; 

return gcd(b%a, a); 
} 
static int gcd(int a, int b) 
{ 
if (a == 0) 
return b; 

return gcd(b%a, a); 
}

static class FastReader{

byte[] buf = new byte[2048];
int index, total;
InputStream in;

FastReader(InputStream is) {
in = is;
}

int scan() throws IOException {
if (index >= total) {
index = 0;
total = in.read(buf);
if (total <= 0) {
return -1;
}
}
return buf[index++];
}

String next() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan());
StringBuilder sb = new StringBuilder();
for (; c > 32; c = scan()) {
sb.append((char) c);
}
return sb.toString();
}

int nextInt() throws IOException {
int c, val = 0;
for (c = scan(); c <= 32; c = scan());
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}

long nextLong() throws IOException {
int c;
long val = 0;
for (c = scan(); c <= 32; c = scan());
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}
}

static class Reader 
{ 
final private int BUFFER_SIZE = 1 << 16; 
private DataInputStream din; 
private byte[] buffer; 
private int bufferPointer, bytesRead; 

public Reader() 
{ 
din = new DataInputStream(System.in); 
buffer = new byte[BUFFER_SIZE]; 
bufferPointer = bytesRead = 0; 
} 

public Reader(String file_name) throws IOException 
{ 
din = new DataInputStream(new FileInputStream(file_name)); 
buffer = new byte[BUFFER_SIZE]; 
bufferPointer = bytesRead = 0; 
} 

public String readLine() throws IOException 
{ 
byte[] buf = new byte[64]; // line length 
int cnt = 0, c; 
while ((c = read()) != -1) 
{ 
if (c == '\n') 
break; 
buf[cnt++] = (byte) c; 
} 
return new String(buf, 0, cnt); 
} 

public int nextInt() throws IOException 
{ 
int ret = 0; 
byte c = read(); 
while (c <= ' ') 
c = read(); 
boolean neg = (c == '-'); 
if (neg) 
c = read(); 
do
{ 
ret = ret * 10 + c - '0'; 
} while ((c = read()) >= '0' && c <= '9'); 

if (neg) 
return -ret; 
return ret; 
} 

public long nextLong() throws IOException 
{ 
long ret = 0; 
byte c = read(); 
while (c <= ' ') 
c = read(); 
boolean neg = (c == '-'); 
if (neg) 
c = read(); 
do { 
ret = ret * 10 + c - '0'; 
} 
while ((c = read()) >= '0' && c <= '9'); 
if (neg) 
return -ret; 
return ret; 
} 

public double nextDouble() throws IOException 
{ 
double ret = 0, div = 1; 
byte c = read(); 
while (c <= ' ') 
c = read(); 
boolean neg = (c == '-'); 
if (neg) 
c = read(); 

do { 
ret = ret * 10 + c - '0'; 
} 
while ((c = read()) >= '0' && c <= '9'); 

if (c == '.') 
{ 
while ((c = read()) >= '0' && c <= '9') 
{ 
ret += (c - '0') / (div *= 10); 
} 
} 

if (neg) 
return -ret; 
return ret; 
} 

private void fillBuffer() throws IOException 
{ 
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
if (bytesRead == -1) 
buffer[0] = -1; 
} 

private byte read() throws IOException 
{ 
if (bufferPointer == bytesRead) 
fillBuffer(); 
return buffer[bufferPointer++]; 
} 

public void close() throws IOException 
{ 
if (din == null) 
return; 
din.close(); 
} 
}
static PrintWriter out=new PrintWriter(System.out);
static int int_max=Integer.MAX_VALUE;
static int int_min=Integer.MIN_VALUE;
static long long_max=Long.MAX_VALUE;
static long long_min=Long.MIN_VALUE;
}
// Thank You !

PYTHON

for tc in range(int(input())):
N, M = map(int, input().split())
X, Y = map(int, input().split())
A, B = map(int, input().split())

def manhatten(x1, y1, x2, y2):
if y2 < y1 or x2 < x1:
return 9999999999999999999999999999999999999999999999999
dx, dy = abs(x1 - x2), abs(y1 - y2)
return dx + dy

def dist(x1, y1, x2, y2):
if y2 < y1 or x2 < x1:
return 99999999999999999999999999999999999999999999
dx, dy = abs(x1 - x2), abs(y1 - y2)
return max(dx, dy)

if manhatten(X, Y, N, M) <= dist(A, B, N, M):
print("YES")
else:
print("NO")

Thief and Police solution, Thief and Police solution, Thief and Police solution, 

Also read : Flower Sequence solution codechef 2021 

Thief and Police solution, Thief and Police solution, Thief and Police solution, Thief and Police solution, Thief and Police solution, Thief and Police solution, Thief and Police solution, Thief and Police solution, Thief and Police solution,

Leave a Comment