Description

Consider an N-by-N chessboard and N pieces of castles. Your task is to find the number of possible ways to put the N castles on the chessboard such that there are no conflicts between any castles. The chessboard consists of K broken grids and you cannot put the castles on those grids.
For example, if N=3, K=2, and the broken grids are (0,0) and (0,2), then your answer is 2 because there are only two feasible solutions:

x#-
#--
x-#

x-#
#--
x#-

Input

The first line of the input is an integer indicating the number N of castles.
The second line contains an integer indicating the number K of broken grids.
Each of the following K lines contains a pair of integers indicating the position (row, column) of one of the K broken grids. N < 30 and K < N*N.
The index for row and column starts from 0.

Output

The number of feasible solutions.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two positive integers a and b, compute the greatest common divisor (GCD) of a and b. The GCD of a and b is the biggest integer that can divide a and b with no reminder.

Input

First line contains a positive integer t (t<=1000), which indicates the number of test cases in the input. In the next t lines, each line contains two positive integers a, b, which are smaller than or equal to 10⁶.

Output

For each case, output the GCD of a and b in a line.

Note that you have to printf "\n" in the end.
 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an m ✕ n matrix A, please calculate the k-by-k max-pooling of A.
Both m and n are multiples of k.
The computation of k-by-k max-pooling is to find the maximum for each k-by-k block of A.
For example, if k is 2 and A is

1 2 3 4 5 6
6 5 4 3 2 1
9 8 7 6 5 4
4 5 6 7 8 9

, then the output should be

6 4 6
9 7 9

because they are the maximal values of the partitions:

1 2|3 4|5 6
6 5|4 3|2 1
--------------
9 8|7 6|5 4
4 5|6 7|8 9

Note: This is a partial judge problem. We have already handled the input and output for you. All you have to do is to implement the function "max_pooling". You are allowed to define another function to support the max_pooling function. However, the downloaded partial judged file should strictly not be changed.

void max_pooling(int A[500][500], int H, int W, int k)

Input

The first line contains three integers m, n, and k, representing the dimensions m, n of matrix A and the size of the block.
The next m lines are elements of the matrix [Aij], i = 0...(m-1) and j = 0...(n-1)

It is guaranteed that 1 ≤ m, n ≤ 500 and k is either 2 or 3

Notice that if k = 2, m and n can be divided by 2, and so on.

We have already handled the input for you.

Output

Please print the result of k-by-k max-pooling.

We have already handled the output for you.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12277.c

Partial Judge Header

12277.h

Tags

Discuss

Description

Each chessboard has integer scores in the range from 0 to 100 written on each grid, and it is provided with 8 pieces of queens.

The task is to place the 8 queens on the chessboard such that no queen takes another one and the sum of scores on the grids occupied by the queens is maximized .

(Rule: each row, column, and diagonal can only have one queen.)

 

Input

The first line of the input is an integer T indicating the number of test cases.

The following lines contain T sets of numbers for the T test cases.

Each set has 64 numbers indicating the scores of the chessboard,  amd each number will be a non-negative integer no larger than 100. 

Each test case is separated by a blank line. T <= 20.

 

Output

The output contains T lines.

Each line shows the maximum sum of scores for the corresponding test case.

There is a '\n' at the end of each line.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss