| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9164 | Stable Sort |
|
| 9168 | Fibonacci number |
|
| 9172 | Is it a forest? |
|
| 9176 | GCD |
|
| 9180 | String Edit Distance |
|
Description
Input
The input includes multiple test cases. In each test case, the first line contains one integer N. The following N lines specify the name Si and the grade Gi.
1 <= N <= 2*106
1 <= |Si| <= 10
0 <= Gi <= 100 (Gi is an integer.)
Output
Output the result in N lines. Every line contains the name and the grade. If more people’s grades are same, output by input order. (That means it uses stable sort.)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a positive integer N, calculate the N'th Fibonacci number.
Input
For each case a line, there is a positive integer N. ( 1 <= N <= 1000 ) When N equals 0, it is the end of file.
Output
For each case a line, print the N'th Fibonacci number.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a graph, output "Yes" if it's a forest, otherwise "No".
Forest's definition : forest is a set that made up by T tree(s). (T>=0)
Input
For each case, The first line contains two positive integers N and M (2 <= N <= 10000000), and N denotes the number of node. In the next M lines, there will be two integers A and B, denoting the two end points of an edge (A, B).
A,B>=1 , A,B<=N
Each case is separated by a blank line. The input is terminated by two zeros in place of N and M.
Output
For each case a line, output "Yes" if it's a forest, otherwise "No".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given three positive integers a, b, and c, compute the greatest common divisor (GCD) of the three numbers. The GCD of the three numbers is the biggest integer that can divide the three number 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 three positive integers a, b, and c, which are smaller than or equal to 106.
Output
For each case, output the GCD of the three numbers in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Edit distance is to measure the difference between two strings. There are three types of edit operations that can be used to change a given string S:
(1) Substitution: replace a character of S by a different character. For example, “cut” can be changed to “cat” by replacing “u” with “a”.
(2) Insertion: insert a single character into S. For example, “cat” can be changed to “cats” by inserting “s” at the end of “cat”.
(3) Deletion: delete a single character from S. For example, “cats” can be changed to “cat” again by deleting “s” from “cats”.
Given two strings S1 and S2, the edit distance between S1 and S2 is defined as the minimum number of edit operations required to transform S1 to S2.
Input
Each case consists of two lines. Each line contains a string of lowercase characters, with the first line representing S1 and the second representing S2. The length of each string is no more than 4000.
Output
Print the edit distance between S1 and S2.
Hint
Suppose that S1 and S2 are strings with n and m characters, respectively. Let S1[1..n] and S2[1..m] denote these two strings. Now, we can define a function Dist(x, y) to give the edit distance between the strings S1[1..x] and S2[1..y]. It is easy to check that Dist(x, y) satisfies the following rules:
●Dist(x, 0) = x for all x = 0, 1, 2, …, n;
●Dist(0, y) = y for all y = 0, 1, 2, …, m;
●Dist(x, y) = min { Dist(x – 1, y)+1, Dist(x, y – 1)+1, Dist(x – 1, y – 1)+a } if x > 0 and y > 0, where a = 1 if S1[x] is not the same as S2[y]; otherwise, a = 0.
The required answer will be the value of Dist(n, m).
You should store the value of each entry Dist(i, j) or you may not pass all of the test case