# N Queen Problem

Problem: Given an n x n grid, how would you place n queens so that no two are attacking. Two queens are said to be attacking if they are on the same row, column or diagonal. The naive solution to this problem will require finding all the permutations i.e. finding all the n! arrangements. A typical example of n queen problem is 8 queen problem which requires us to find possible placements of 8 queens on a 8 x 8 chess board. One of the arrangements of 8 x 8 problem is shown below:

The solution of this problem can be thought as follows:

- We start from the first row and proceed to next row till the last row.
- if next queen to be placed has same column value as already placed queen has then don’t place the queen. This can be checked by traversing from i=1 to i= k-1 where k is the next row where the queen is to be placed.
- if next queen to be placed lies in any of the diagonals of already placed queens then don’t place the queen. This can be done by merely checking (abs(i-k)==abs(j-l)) where (i,j) is the place of any existing queen and (k,l) is the position of the next queen i.e. kth row and ith column.

# Trace the Rats

Given a square maze **(A)** of dimension **N**, every entry **(Aij)** in the maze is either an open cell **‘O’** or a wall **‘X’**. A rat can travel to its adjacent locations (left, right, top and bottom), but to reach a cell, it must be open. Given the locations of **R **rats, can you find out whether all the rats can reach others or not?

**Input Format:**

Input will consist of three parts, viz.

1. Size of the maze (N)

2. The maze itself (A = N * N)

3. Number of rats (R)

4. Location of R rats (X_{i}, Y_{i})

**Note: **

- (Xi, Yi) will represent the location of the ith rat.
- Locations are 1-index based.

**Output Format:**

**Constraints:**

**1<=N<=350**

**Aij = {‘O’,’X’}**

**1<=R<=N*N**

**1<=Xi<=N**

**1<=Yi<=N**

**Sample Input and Output**

Sno. | Input | Output |
---|---|---|

1 | 3 O O X O X O O O X 4 1 1 1 2 2 1 3 2 | Yes |

2 | 3 O O X O X O O O X 4 1 1 1 2 2 1 2 3 | No |

# Isotope Fusion

Scientists recently found a new element X, which can have different isotopes upto an atomic value of 199. Speciality of element X is that when two atoms fuse they produce energy multiple of their atomic value and forms an atom with atomic value of their multiple modulus 199.

For Eg:

If atom1 with value 56 and atom2 with value 61 fuses.

They produce energy of 3416 KJ (56 * 61)

Resulting atom will have atomic value (56*61) mod 199 = 33

Scientists created a nuclear reactor to create energy by this method. Every day they get several atoms of X from a supplier in a particular sequence. Since this element highly radioactive they can’t risk by changing its sequence. So each atom can fuse only with another atom nearby. Nevertheless, scientists can choose an order of fusion thereby maximizing total energy produced.

Now, for given sequence of atomic values, output maximum energy that can be produced.

## Eample

If sequence of atoms are

56,61, 2

Then they can produce 3416KJ by fusing 56&61 which result in an atom of value 33. Then they can fuse 33 and 2 to get the energy of 66KJ. So total energy generated is 3482.

But if they cleverly choose to fuse atoms 61 & 2 first then they generate 122 KJ with a resulting atom of value 122. Then if they fuse 122 and 56, they can generate 6832 KJ. So total energy is 6954.

Hence Maximum energy that can be generated from this sequence is 6954.

### Input Format

Line 1 | N, where N is the number of atoms in the sequence to be fused. |

Line 2 | a_{1} a_{2} a_{3} …. a_{n}where ai -> Atomic value of i th atom. and two atoms are space delimited |

**Output Format**

Line 1 | For Valid InputE,where E is Integer stating maximum energy that can be produced For Invalid InputINVALID INPUT |

**Sample Inputs and Outputs**

Sr.no | Input | Output(Rounded upto Three Decimal digits) |

1 | 3 15 75 60 | 8925 |

2 | J | INVALID INPUT |

3 | 3 15 0 6 | INVALID INPUT |

4 | 3 5 5 199 | INVALID INPUT |

5 | 4 15 75 60 45 | 18515 |

**Limit the Method Instructions**

Raj is a newbie to the programming and while learning the programming language he came to know the following rules:

– Each program must start with ‘{‘ and end with ‘}’.

– Each program must contain only one main function. Main function must start with ‘<‘ and end with ‘>’.

– A program may or may not contain user defined function(s). There is no limitation on the number of user defined functions in the program. User defined function must start with ‘(‘ and end with ‘)’.

– Loops are allowed only inside the functions (this function can be either main function or user defined function(s)). Every loop must start with ‘{‘ and end with ‘}’.

– User defined function(s) are not allowed to be defined inside main function or other user defined function(s).

– Nested loops are allowed.

– Instructions can be anywhere inside the program.

– Number of instructions inside any user defined function must not be more than 100.

If any of the above conditions is not satisfied, then the program will generate compilation errors. Today Raj has written a few programs, but he is not sure about the correctness of the programs. Your task is to help him to find out whether his program will compile without any errors or not.

**Input Format:**

First line starts with ** T**, number of test cases. Each test case will contain a single line

**, where**

**L****is a program written by Raj.**

**L****Output Format:**

Print “No Compilation Errors” if there are no compilation errors, else print “Compilation Errors”.

**Constraints:**

1<=T<=100

L is a text and can be composed of any of the characters {, }, (, ), <, >and P, where P will represents the instruction.

L, comprised of characters mentioned above should be single spaced delimited.

Number of characters in the text, |L| < = 1000**0**

SNo. | Input | Output |
---|---|---|

1 | 3 { < > ( P ) } { < { } > ( { } ) ) { ( { } ) } | No Compilation Errors Compilation Errors Compilation Errors |