# A Chessboard Game

### Problem Statement :

```Two players are playing a game on a  chessboard. The rules of the game are as follows:

The game starts with a single coin located at some  coordinates. The coordinates of the upper left cell are , and of the lower right cell are .

In each move, a player must move the coin from cell  to one of the following locations:

Note: The coin must remain inside the confines of the board.

Beginning with player 1, the players alternate turns. The first player who is unable to make a move loses the game.

The figure below shows all four possible moves using an  board for illustration:

Function Description

Complete the chessboardGame function in the editor below. It should return a string, either First or Second.

chessboardGame has the following parameter(s):

x: an integer that represents the starting column position
y: an integer that represents the starting row position

Input Format

The first line contains an integer , the number of test cases.
Each of the next  lines contains  space-separated integers  and .```

### Solution :

```                            ```Solution in C :

In  C :

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t;
scanf("%d",&t);
while(t--)
{
int x,y;
scanf("%d %d",&x,&y);
int dp;
x--;
y--;
dp=dp=dp=dp=1;
int i=2;
while(i<15)
{
int temp=0;
while(temp<=i)
{
if((i-2>=0&&temp+1<15?dp[i-2][temp+1]:0)||(i-2>=0&&temp-1>=0?dp[i-2][temp-1]:0)||(i+1<15&&temp-2>=0?dp[i+1][temp-2]:0)||(i-1>=0&&temp-2>=0?dp[i-1][temp-2]:0))
dp[i][temp]=0;
else
dp[i][temp]=1;
if((i-2>=0&&temp+1<15?dp[temp+1][i-2]:0)||(i-2>=0&&temp-1>=0?dp[temp-1][i-2]:0)||(i+1<15&&temp-2>=0?dp[temp-2][i+1]:0)||(i-1>=0&&temp-2>=0?dp[temp-2][i-1]:0))
dp[temp][i]=0;
else
dp[temp][i]=1;
temp++;
}
i++;
}
if(dp[x][y])
printf("Second\n");
else
printf("First\n");
}
return 0;
}```
```

```                        ```Solution in C++ :

In  C++  :

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
long DP;
long dx={-2,-2,1,-1};
long dy={1,-1,-2,-2};
bool inside(long u,long v)
{
return (u>0 && v>0 && u<=15 && v<=15);
}

bool dp(long x,long y)
{
if (DP[x][y]!=-1) return DP[x][y];
bool res=false;
for (long i=0; i<4; ++i)
{
long xx=x+dx[i],yy=y+dy[i];
if (inside(xx,yy)) res=res|(!dp(xx,yy));
}
DP[x][y]=res;
return res;
}
int main()
{
long nTest,x,y;
memset(DP,-1,sizeof(DP));
DP=DP=DP=DP=false;
scanf("%ld",&nTest);
while (nTest--)
{
scanf("%ld%ld",&x,&y);
puts(dp(x,y)?"First":"Second");
}
}```
```

```                        ```Solution in Java :

In   Java :

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

private static void pasteTessalation(boolean[][] board, int r, int c) {
board[r][c] = true;
board[r][c+1] = true;
board[r+1][c] = true;
board[r+1][c+1] = true;
}

public static void main(String[] args) {
boolean[][] loss = new boolean;
for (int i=0; i<16; i+=4) {
for (int j=0; j<16; j+=4) {
pasteTessalation(loss,i,j);
}
}
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t=0; t<T; t++) {
int r = sc.nextInt()-1;
int c = sc.nextInt()-1;
if (loss[r][c]) {
System.out.println("Second");
} else {
System.out.println("First");
}
}

}

}```
```

```                        ```Solution in Python :

in    Python3 :

import copy

move = [(-2,1),(-2,-1),(1,-2),(-1,-2)]
grid_copy = set()
for i in range(1,16):
for j in range(1,16):

First = set()
Second = set()

t=0
while len(First) + len(Second) != 225:
if t%2 ==0:
for i,j in grid_copy:
n=0
for x,y in move:
if (i+x,j+y) not in grid_copy or (i+x,j+y) in First:
n+=1
if n==4:
else:
for i,j in grid_copy:
for x,y in move:
if (i+x,j+y) in Second:
t+=1
#print('--------')
#print(sorted(list(First)))
#print(len(First))
#print(sorted(list(Second)))
#print(len(Second))
test = int(input())
for _ in range(test):
x,y = map(int,input().strip().split())
if (x,y) in First:
print('First')
else:
print('Second')```
```

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty