Description

Writer: jjjjj19980806       Description: pclightyear        Difficulty: ★★★☆☆

In mathematics, a Markov matrix is a square matrix used to describe the transitions of a Markov chain. Each of its entries is a nonnegative real number representing a probability. It has found use throughout a wide variety of scientific fields, including population genetics.

Consider a country with n cities. Originally, each city has its own population, which can be described as a state vector X₀. As the time pass by, the population will move from one city to another. The whole progress can be described as a n × n Markov matrix A.

In this problem, if the state vector of the city population now is X_n, after a year, the state vector will become X_n+1, where X_n+1 = AX_n.

Now, you are given the original population in each city by a state vector X₀ and the Markov matrix A. You need to calculate how many years it takes to let the first city’s population to drop below or equal to a specific number p, or it will never drop below p.

Input

The first line contains an integer T, representing the number of test cases.

For each test case:

The first line contains an integer n, representing the number of the cities.

The next n lines contain n floating-point number a_ij, representing each entry in the Markov matrix A.

The next line contains n integers X_i, representing each entry in the state vector X₀.

The next line contains an integer p, representing the specific number of population.

It is guaranteed that:

• 1 ≤ T ≤ 5
• 1 ≤ n ≤ 5
• 0 ≤ X_0i ≤ 10⁶

Output

Please output how many years it takes to let the first city’s population to drop below p, or output "Never" if it will never drop below p.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Writer: jjjjj19980806       Description: pclightyear        Difficulty: ★★★★★

As you all know, Kim Jong-un is the Chairman of the Workers' Party of Korea and supreme leader of North Korea. Recently, more and more countries and international bodies have been imposing economic sanctions against North Korea. The import of the raw material of all kind decreases dramatically, and the automobile industry in North Korea is suffering from severe depression again. Reorganization of the whole industry is needed to make North Korea GREAT AGAIN.

According to the survey, there are n factory in North Korea. Each of them can produce two kinds of cars (car A & car B). Now, the supreme leader wants to assign x factory to produce car A and y factory to produce car B (i.e. no factory will produce two kinds of car at the same time.) so that the net profit will become maximum. However, due to the shortage of the raw material, it is possible that some factory will not produce any cars (i.e. x + y <= n).

The supreme leader will give you the net profit each factory can make by producing car A and car B. Your program need to output the name of the x factory which produce car A in lexicographical order. If there are multiple answers, you need to output the one such that the total net profit of car A is maximum. 

DO NOT DISAPPOINT HIM!!

Input

The first line contains three integers n, x, y, representing the total number of factory, the number of factory planned to produce car A, and the number of factory planned to produce car B. (according to the supreme leader's demand)

The next n lines contains one string s_i and two integers a_i, b_i, representing the name of each factory, and the net profit each factory can make by producing only car A or only car B.

It is guaranteed that :

• 0 < n, x, y ≤ 500
• x + y <= n
• 1 ≤ | s_i | ≤  20
• 0 < a_i, b_i < 10⁶
• a_i ≠ a_j, b_i ≠ b_j  if i ≠ j.
• No duplicate names appears.

Output

Please output the list of x factory that need to produce car A in lexicographical order so that it will maximum the net profit.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Writer: jjjjj19980806       Description: pclightyear        Difficulty: ★★☆☆☆

Given a list of students and their score, you have to sort their score in decreasing order.

If there are many students with the same score, you need to maintain their relative order in the original list.

That is, if whenever there are two students A and B with the same score and with A appearing before B in the original list, A will appear before B in the sorted list.

Reference: https://en.wikipedia.org/wiki/Category:Stable_sorts​

Input

The first line contains one integer n, representing the number of students.

The next n lines contain a string and an integer s_i and a_i, representing the name of each student and his/her score.

It is guaranteed that :

• n ≤ 10⁵
• 1 ≤ | si | ≤ 20
• 0 ≤ a_ij ≤ 100

Output

After sorting, please output the list of students' names, each name with a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Writer: jjjjj19980806       Description: pclightyear        Difficulty: ★★★☆☆

In linear algebra, the determinant (行列式) is a useful value that can be computed from the elements of a square matrix. The determinant also has many useful properties. For example: Assume we have a square matrix A. Then the determinant of A equals to zero if and only if A is not invertible.

Given a n × n square matrix A, you have to calculate the determinant of A. (Denoted by det(A))

Note: 

(1) We can define the determinant of a 2 × 2 matrix as below:

(2) We can calculate the determinant of a 3 × 3 matrix as below:

Input

The first line contains one integer n, representing the size of A.

The next n lines contains n integers a_ij, representing each entry in A.

It is guaranteed that :

• 1 ≤ n ≤ 8
• -16 ≤ a_ij ≤ 15

Note that det(A) may exceed INT.

Output

Please output a line contains the value of det(A).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Writer: jjjjj19980806       Description: pclightyear        Difficulty: ★☆☆☆☆

Given a linked list, you have to reverse it and output the result.

You have to implement four function:

1. Node* Create_List(Node*, int);

This function is used to create the linked list according to the input.

2. Node* Reverse_List(Node*);

This function is used to reverse the given linked list.

3. void Print_List(Node*);

This function is used to print out the key value in the linked list.

4. void Free_List(Node*);

This function is used to free the memory space.

Input

The first line contains one integer n, representing the number of nodes in the linked list.

The next lines contains n integers, each integer represents a node in the linked list.

It is guaranteed that :

• 1 ≤ n ≤ 10
• 0 ≤ a_i ≤ 100

Output

You need to output the reversed linked lists.

Each key value is separated by "->".

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Writer: jjjjj19980806       Description: pclightyear        Difficulty: ★★★★☆

Given an undirected graph G, you have to check whether it is a bipartite graph (二分圖) or not.

Input

The first line contains an integer T, representing the number of test cases.

For each test case:

The first line contains two integers n, m, representing the number of vertices and the number of edges.

The next m lines contain two integers u, v, representing that there is an undirected edge between vertex u and vertex v.

It is guaranteed that:

• 1 ≤ T ≤ 10
• 2 ≤ n ≤ 1000
• n-1 ≤ m ≤ n²
• 1 ≤ u, v ≤ 1000
• NO multiple edge
• NO self cycle
• the graph is connected

Output

For each graph G, if G is a bipartite graph, please output "Yes", otherwise please output "No".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Writer: jjjjj19980806       Description: pclightyear        Difficulty: ★★★☆☆

Given n numbers, you need to find a number k such that SUM is minimum,

where we define SUM = ( a₁ ^ k ) + ( a₂ ^ k ) + ... + ( a_n ^ k )

(^ stands for the "xor" bitwise operation of the two operand)

Input

The first line contains an integer n, representing the number of numbers.

The next line contains n integers a_i, representing each given number.

It is guaranteed that:

• n ≤ 10⁵
• 0 ≤ a_i ≤ 10⁶
• All numbers ( a_i and k ) are unsigned numbers

Output

Please output the value of SUM.

Note SUM may exceed INT.

Sample Input  Download

Sample Output  Download

Tags

Discuss