| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11788 | XOR |
|
| 11789 | F - Bipartite Graph |
|
| 11810 | C - Stable Sort |
|
| 11811 | Determinant |
|
| 11812 | Markov Matrix |
|
Description
Given n numbers, you need to find a number k such that SUM is minimum,
where we define SUM = ( a1 ^ k ) + ( a2 ^ k ) + ... + ( an ^ k )
(^ stands for the "xor" bitwise operation of the two operand)
original problem: https://acm.cs.nthu.edu.tw/problem/11770/
Input
The first line contains an integer n, representing the number of numbers.
The next line contains n integers ai, representing each given number.
It is guaranteed that:
- n ≤ 105
- 0 ≤ ai ≤ 106
- All numbers ( ai 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
Description
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 ≤ 5
- 2 ≤ n ≤ 1000
- n-1 ≤ m ≤ n2
- 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 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 si and ai, representing the name of each student and his/her score.
It is guaranteed that :
- n ≤ 105
- 1 ≤ | si | ≤ 20
- 0 ≤ aij ≤ 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
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 aij, representing each entry in A.
It is guaranteed that :
- 1 ≤ n ≤ 8
- -16 ≤ aij ≤ 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
n 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 vectorX0. 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 Xn, after a year, the state vector will become Xn+1, whereXn+1 = AXn.
Now, you are given the original population in each city by a state vector X0 and the Markov matrix A. You need to calculate how many years it takes to let the first city’s population to drop below a specific number p, or it will never drop below p after reaching steady state.
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 aij, representing each entry in the Markov matrix A.
The next line contains n integers Xi, representing each entry in the state vector X0.
The next line contains an integer p, representing the specific number of population.
It is guaranteed that:
- 1 ≤ T ≤ 5
- 1 ≤ n ≤ 5
- 0 ≤ aij ≤ 106
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 after reaching steady state.